[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