Differences between revisions 21 and 22
 ⇤ ← Revision 21 as of 2007-09-05 21:50:43 → Size: 5100 Editor: RogerHui Comment: ← Revision 22 as of 2008-12-08 10:45:45 → ⇥ Size: 5028 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 4: Line 4: Problem posed by Kip Murray to the [wiki:JForum:programming/2005-December/000313 J programming forum] Problem posed by Kip Murray to the [[JForum:programming/2005-December/000313|J programming forum]] Line 29: Line 29: `ndiv `is from the [:Essays/Divisors:divisors page].` nufs `works with` n `rather `ndiv `is from the [[Essays/Divisors|divisors page]].` nufs `works with` n `rather Line 129: Line 129: `div `is from the [:Essays/Divisors:divisors page];` div n `are all the divisors of` n` . `div `is from the [[Essays/Divisors|divisors page]];` div n `are all the divisors of` n` . Line 165: Line 165: [[BR]] <
> Line 168: Line 168: * [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A018892 On-line Encyclopedia of Integer Sequences A018892] * [:Essays/Egyptian Fraction:Egyptian Fraction] * [[OEIS:A018892|On-line Encyclopedia of Integer Sequences A018892]] * [[Essays/Egyptian Fraction|Egyptian Fraction]] Line 171: Line 171: [[BR]] <
>

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```