Puzzles/Unit Fraction Sum
Problem posed by Kip Murray to the J programming forum on 2005-12-01.
How many ways can a unit fraction 1%n be expressed as a sum of unit fractions 1%x and 1%y ?
Solution
A unit fraction sum (ufs) can be expressed as (1%n+r)+(1%n+s) where r and s are integers greater than 0, and:
(1%n) = (1%n+r) + (1%n+s) (1%n) = ((n+s) + (n+r)) % (n+r) * (n+s) ((n+r)*(n+s)) = n * (n+s) + n+r ((n^2)+(n*r)+(n*s)+(r*s)) = (n^2)+(n*s)+(n^2)+(n*r) (r*s) = n^2
Since the above steps are reversible, the ufs are all the ways of expressing n^2 as the product of two integers. The number of ufs is therefore the number of divisors of n^2 . If the ordering does not matter, that is, if (1%x)+(1%y) is considered the same as (1%y)+(1%x) , then that number is -:1+ndiv n^2 .
ndiv is from the divisors page. nufs works with n rather than n^2 since the latter can be a lot harder to factor.
ndiv=: */ @: >: @: {: @: (__&q:)
nufs=: 3 : '-: >: */ >: +: {: __ q: y'
ndiv 12^2
15
-: 1 + ndiv 12^2
8
nufs 12
8
The actual unit fraction sums can be produced as follows:
rs=: 3 : 0 n=. x: y 'p e'=. __ q: n b=. >:+:e (*:n) (] ,. %) */"1 p^"1 b #: i.-:1+*/b ) ufs=: 3 : 0 n=. x: y z=. % n + rs n assert. ~: z assert. (%n) = +/"1 z assert. (=<.) %z ) rs 12 1 144 3 48 9 16 2 72 6 24 18 8 4 36 12 12 ufs 12 1r13 1r156 1r15 1r60 1r21 1r28 1r14 1r84 1r18 1r36 1r30 1r20 1r16 1r48 1r24 1r24 +/"1 ufs 12 1r12 1r12 1r12 1r12 1r12 1r12 ufs&.> 6 9 12 19 144 ┌─────────┬─────────┬──────────┬──────────┬─────────────┐ │ 1r7 1r42│1r10 1r90│1r13 1r156│1r20 1r380│1r145 1r20880│ │ 1r9 1r18│1r12 1r36│1r15 1r60│1r38 1r38│1r147 1r7056│ │1r15 1r10│1r18 1r18│1r21 1r28│ │1r153 1r2448│ │ 1r8 1r24│ │1r14 1r84│ │1r171 1r912│ │1r12 1r12│ │1r18 1r36│ │1r225 1r400│ │ │ │1r30 1r20│ │1r146 1r10512│ │ │ │1r16 1r48│ │1r150 1r3600│ │ │ │1r24 1r24│ │1r162 1r1296│ │ │ │ │ │1r198 1r528│ │ │ │ │ │1r306 1r272│ │ │ │ │ │1r148 1r5328│ │ │ │ │ │1r156 1r1872│ │ │ │ │ │1r180 1r720│ │ │ │ │ │1r252 1r336│ │ │ │ │ │1r468 1r208│ │ │ │ │ │1r152 1r2736│ │ │ │ │ │1r168 1r1008│ │ │ │ │ │1r216 1r432│ │ │ │ │ │1r360 1r240│ │ │ │ │ │1r792 1r176│ │ │ │ │ │1r160 1r1440│ │ │ │ │ │1r192 1r576│ │ │ │ │ │1r288 1r288│ └─────────┴─────────┴──────────┴──────────┴─────────────┘
Another Solution
Let c and d be divisors of n . Then:
(1%n) = (1%n) * (c+d)%(c+d) (1%n) = (1%n) * (c%c+d) + (d%c+d) (1%n) = ((1%n) * c%c+d) + ((1%n) * d%c+d) (1%n) = (1%(n%c)*c+d) + (1%(n%d)*c+d)
Since c and d are divisors of n , n%c and n%d are integers and so are (n%c)*c+d and (n%d)*c+d , with the latter two the x and y that we seek. To avoid duplicates, we choose c and d to satisfy c<:d and 1=c+.d .
div is from the divisors page; div n are all the divisors of n .
div=: /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:) cd=: 3 : 0 (,(<:/~d)*.1=+./~d) # ,/,"0/~d=. div x: y ) ufs2=: 3 : 0 n=. x: y z=. % n (% * +/"1@]) cd n assert. ~: z assert. (%n) = +/"1 z assert. (=<.) %z ) ufs2 12 1r24 1r24 1r36 1r18 1r48 1r16 1r60 1r15 1r84 1r14 1r156 1r13 1r30 1r20 1r28 1r21
r,s and c,d are related as follows:
(% +./"1) n + rs n NB. c,d from r,s n -~ n (% * +/"1@]) cd n NB. r,s from c,d
See also
Contributed by Roger Hui.