Puzzles/Unit Fraction Sum

From J Wiki
Jump to: navigation, search

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.