[seqfan] Re: Puzzle

Matthijs Coster seqfan at matcos.nl
Fri Jan 23 15:48:19 CET 2015


Dear Bob,

I improved my program. And the final program is comparable to your 
suggestion.
Considering r, I start with 1 and subtract r from 1 as many time as 
possible. For each possibility I calculate the reciprocal. I create a 
list with elements which are 3-tuples: (d,z, zz) where d = 
denominator(zz) z previous number; zz number in research. The list is 
sorted on the denominator. Each time I use the element with the smallest 
denominator and apply the main step (subtract r as many times as 
possible and take the reciprocal).

In formula:

zz = 1/(z+kr), where ceiling(z/r-1/r^2) < k < floor(z/r)

It is very important to use all the elements which occur by choosing k. 
I conjecture that it is much harder to find solutions for p/p+2, for 
large p, since generally there is only one occurrence of k.

I have up to now the following results (length) [fractions]:
->  10/27 -> (18) [621, 7803/23, 429/289, 573/143, 3231/191, 819/359, 
141/91, 4887/47, 471/181, 1107/157, 21/41, 37/7, 4077/37, 1791/151, 
459/199, 297/17, 21/11, 27/7]
->  13/18 -> (18 [35/9, 1374/35, 502/229, 1746/251, 84/97, 93/28, 
890/279, 26172/445, 14751/2908, 5058/1639, 294/281, 153/49, 693/17, 
558/77, 1773/31, 288/197, 45/32, 18/5]
->  7/9 -> (20) [15, 12/5, 627/4, 489/209, 450/163, 57/50, 593/19, 
53982/593, 4731/5998, 5679/1577, 666/631, 1509/74, 9414/503, 1683/1046, 
2007/187, 888/223, 765/296, 99/85, 18/11, 9/2]
->  7/17 -> (20) [204, 425/12, 11/25, 102/11, 1105/6, 23018/65, 
3349/1354, 323/197, 2210/19, 697/130, 15742/41, 765/926, 73/45, 
20485/73, 1989/1205, 13753/117, 340/809, 2057/20, 51/121, 17/3]
->  13/20 -> (25) [44/5, 180/11, 100/9, 37/50, 43340/37, 8455/4334, 
9660/1691, 3538/483, 11740/1769, 470/587, 5245/188, 2765/1049, 
516380/553, 16810/25819, 389380/1681, 88668/19469, 76910/22167, 
12215/7691, 7890/2443, 1270/789, 244/127, 230/61, 36/23, 35/9, 20/7]
->  13/21 -> (26) [105, 28/15, 17/4, 44646/17, 85547/2126, 45696/12221, 
1929/2176, 23016/643, 3423/1096, 254/163, 72807/254, 6475/10401, 
11793/925, 34377/3931, 31602/1637, 46193/10534, 50526/6599, 5411/7218, 
4529/2319, 3936/647, 5901/1312, 12712/843, 3493/1816, 4893/499, 168/233, 
21/8]
->  7/11 -> (66) [113, 792/113, 8899/72, 1551/809, 253/141, 891/23, 
27115/81, 1576/2465, 134849/1576, 1061104/12259, 185273/96464, 
30206/16843, 277629/2746, 1092410/25239, 128689/99310, 16473/11699, 
357632/16473, 22187/32512, 112057/2017, 6666/10187, 6325/606, 421/575, 
9416/421, 583/856, 41360/53, 7183/3760, 2004/653, 239129/2004, 
27850/21739, 216689/27850, 40139/19699, 6435/3649, 704/585, 379/64, 
2717/379, 506/247, 1369/46, 728354/1369, 126533/66214, 49940/11503, 
9713/4540, 17270/883, 19063/1570, 4554/1733, 421/414, 3361/421, 
165110/3361, 2235431/15010, 130687/203221, 2947648/130687, 
693981/267968, 5125835/693981, 656161/465985, 80322/59651, 70477/7302, 
4741/6407, 1850552/431, 856493/168232, 609884/77863, 42361/55444, 
7491/3851, 3817/681, 1166/347, 99/106, 44/9, 11/4]

While quite a lot of fractions do not lead to a (small) solution. e.g. 
5/23, 5/29, 9/11, 10/17, 10/29, 11/13, 11/14, 11/17, 11/19, etc...



Best regards,

Matthijs Coster


> Denote reciprocals as R_(f) where f is any positive real rational number.
>
> Take R_(1 - i*a/b) {i = 1..j} where j is the maximum value such that 
> j*a < b.  If any value of k generates an integer for R_(1 - i*a/b), 
> then certainly the fraction a/b is a solution.
>
> Ex. 1.  3/8:  R_(1-3/8) = 8/5; R_(1-6/8) = 4.  So we can start with 1 
> = 8/8 and add 3/8 until we reach 32/8 = 4, take R_(4) = 1/4 and add 
> 3/8 + 3/8 to reach 1.
>
> By extension, we can use a "modular chain" (perhaps there's a standard 
> term for this?) for solutions.
>
> Ex. 2.  5/9:  R_(1-5/9) = 9/4.  9/4 = 81/36.  5/9 = 20/36.  81 mod 20 = 1
>
> R_(1/36) = 36.  36 = 324/9.  324 mod 5 = 4.  4/9 + 5/9 = 1.
>
> So we know we can start with 1 = 9/9 and continue to add 5/9 until we 
> reach 324/9 = 36; take R_(36) = 1/36; continue to add 5/9 until we 
> reach 81/36 = 9/4; take R_(9/4) = 4/9 and add 5/9 to reach 1.
>
> I think generally, if we us this approach to where we eventually reach 
> n mod k = 1, we immediately reach a solution, working backwards.
>
> Ex. 3.  7/9.  This is much trickier (done by hand, hopefully no errors):
>
> R_(1-7/9) = 9/2.  9/2 = 81/18.   7/9 = 14/18.  81 mod 14 = 11.
>
> R_(11/18) = 18/11.  18/11 = 162/99.   7/9 = 77/99.  162 mod 77 = 8.
>
> R_(8/99) = 99/8 = 891/72.   7/9 = 56/72.   891 mod 56 = 51.
>
> 51/72 = 17/24.  R_(17/24) = 24/17 = 216/153.   7/9 = 119/153.  216 mod 
> 119 = 97.
>
> R_(97/153) = 153/97 = 1377/873.   7/9 = 679/873.   1377 mod 679 = 19.
>
> R_(19/873) = 873/19 = 7857/171.  7/9 = 133/171.   7857 mod 133 = 10.
>
> R_(10/171) = 171/10 = 1539/90.   7/9 = 70/90.  1539 mod 70 = 69.
>
> 69/90 = 23/30.   R_(23/30) = 30/23 = 270/207.   7/9 = 161/207. 270 mod 
> 161 = 109.
>
> etc.
>
> I think we eventually will reach n mod k =1; I don't have a computer 
> program to verify.
>
> Matthijs - I  see the 2/9 and 11/18 at the bottom of your output, so 
> is this "modular chain" process essentially what your program is 
> doing?  (sorry, I don't understand code).
>
> If not, could someone see with if this works, and is compatible with 
> Matthijs' results?
>
> Cheers,
> Bob S.




More information about the SeqFan mailing list