[seqfan] Re: Puzzle
Bob Selcoe
rselcoe at entouchonline.net
Wed Jan 21 22:54:52 CET 2015
Hi Matthijs and All,
It seems to me that the puzzle should be solvable for (at least) all
positive real rational numbers < 1.
By definition, a/b = c, c < 1.
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.
--------------------------------------------------
From: "Matthijs Coster" <seqfan at matcos.nl>
Sent: Wednesday, January 21, 2015 3:12 PM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: Puzzle
> However there is a solution for r = 7/9:
> I jump immediately from t to 1/(r+t)
>
> 1, 16/9, 23/9, 10/3, 37/9, 44/9, 17/3, 58/9, 65/9, 8, 79/9, 86/9, 31/3,
> 100/9, 107/9, 38/3, 121/9, 128/9, 1/15, 38/45, 73/45, 5/12, 43/36,
> 71/36, 11/4, 127/36, 155/36, 61/12, 211/36, 239/36, 89/12, 295/36,
> 323/36, 39/4, 379/36, 407/36, 145/12, 463/36, 491/36, 173/12, 547/36,
> 575/36, 67/4, 631/36, 659/36, 229/12, 715/36, 743/36, 257/12, 799/36,
> 827/36, 95/4, 883/36, 911/36, 313/12, 967/36, 995/36, 341/12, 1051/36,
> 1079/36, 123/4, 1135/36, 1163/36, 397/12, 1219/36, 1247/36, 425/12,
> 1303/36, 1331/36, 151/4, 1387/36, 1415/36, 481/12, 1471/36, 1499/36,
> 509/12, 1555/36, 1583/36, 179/4, 1639/36, 1667/36, 565/12, 1723/36,
> 1751/36, 593/12, 1807/36, 1835/36, 207/4, 1891/36, 1919/36, 649/12,
> 1975/36, 2003/36, 677/12, 2059/36, 2087/36, 235/4, 2143/36, 2171/36,
> 733/12, 2227/36, 2255/36, 761/12, 2311/36, 2339/36, 263/4, 2395/36,
> 2423/36, 817/12, 2479/36, 2507/36, 845/12, 2563/36, 2591/36, 291/4,
> 2647/36, 2675/36, 901/12, 2731/36, 2759/36, 929/12, 2815/36, 2843/36,
> 319/4, 2899/36, 2927/36, 985/12, 2983/36, 3011/36, 1013/12, 3067/36,
> 3095/36, 347/4, 3151/36, 3179/36, 1069/12, 3235/36, 3263/36, 1097/12,
> 3319/36, 3347/36, 375/4, 3403/36, 3431/36, 1153/12, 3487/36, 3515/36,
> 1181/12, 3571/36, 3599/36, 403/4, 3655/36, 3683/36, 1237/12, 3739/36,
> 3767/36, 1265/12, 3823/36, 3851/36, 431/4, 3907/36, 3935/36, 1321/12,
> 3991/36, 4019/36, 1349/12, 4075/36, 4103/36, 459/4, 4159/36, 4187/36,
> 1405/12, 4243/36, 4271/36, 1433/12, 4327/36, 4355/36, 487/4, 4411/36,
> 4439/36, 1489/12, 4495/36, 4523/36, 1517/12, 4579/36, 4607/36, 515/4,
> 4663/36, 4691/36, 1573/12, 4747/36, 4775/36, 1601/12, 4831/36, 4859/36,
> 543/4, 4915/36, 4943/36, 1657/12, 4999/36, 5027/36, 1685/12, 5083/36,
> 5111/36, 571/4, 5167/36, 5195/36, 1741/12, 5251/36, 5279/36, 1769/12,
> 5335/36, 5363/36, 599/4, 5419/36, 5447/36, 1825/12, 5503/36, 5531/36,
> 1853/12, 5587/36, 5615/36, 4/627, 1475/1881, 2938/1881, 209/489,
> 1768/1467, 2909/1467, 163/450, 50/57, 283/171, 416/171, 61/19, 682/171,
> 815/171, 316/57, 1081/171, 1214/171, 449/57, 1480/171, 1613/171, 194/19,
> 1879/171, 2012/171, 715/57, 2278/171, 2411/171, 848/57, 2677/171,
> 2810/171, 327/19, 3076/171, 3209/171, 1114/57, 3475/171, 3608/171,
> 1247/57, 3874/171, 4007/171, 460/19, 4273/171, 4406/171, 1513/57,
> 4672/171, 4805/171, 1646/57, 5071/171, 5204/171, 19/593, 4322/5337,
> 8473/5337, 4208/1779, 16775/5337, 20926/5337, 8359/1779, 29228/5337,
> 33379/5337, 4170/593, 41681/5337, 45832/5337, 16661/1779, 54134/5337,
> 58285/5337, 20812/1779, 66587/5337, 70738/5337, 8321/593, 79040/5337,
> 83191/5337, 29114/1779, 91493/5337, 95644/5337, 33265/1779, 103946/5337,
> 108097/5337, 12472/593, 116399/5337, 120550/5337, 41567/1779,
> 128852/5337, 133003/5337, 45718/1779, 141305/5337, 145456/5337,
> 16623/593, 153758/5337, 157909/5337, 54020/1779, 166211/5337,
> 170362/5337, 58171/1779, 178664/5337, 182815/5337, 20774/593,
> 191117/5337, 195268/5337, 66473/1779, 203570/5337, 207721/5337,
> 70624/1779, 216023/5337, 220174/5337, 24925/593, 228476/5337,
> 232627/5337, 78926/1779, 240929/5337, 245080/5337, 83077/1779,
> 253382/5337, 257533/5337, 29076/593, 265835/5337, 269986/5337,
> 91379/1779, 278288/5337, 282439/5337, 95530/1779, 290741/5337,
> 294892/5337, 33227/593, 303194/5337, 307345/5337, 103832/1779,
> 315647/5337, 319798/5337, 107983/1779, 328100/5337, 332251/5337,
> 37378/593, 340553/5337, 344704/5337, 116285/1779, 353006/5337,
> 357157/5337, 120436/1779, 365459/5337, 369610/5337, 41529/593,
> 377912/5337, 382063/5337, 128738/1779, 390365/5337, 394516/5337,
> 132889/1779, 402818/5337, 406969/5337, 45680/593, 415271/5337,
> 419422/5337, 141191/1779, 427724/5337, 431875/5337, 145342/1779,
> 440177/5337, 444328/5337, 49831/593, 452630/5337, 456781/5337,
> 153644/1779, 465083/5337, 469234/5337, 157795/1779, 477536/5337,
> 481687/5337, 593/53982, 5998/4731, 29033/14193, 40072/14193, 1577/5679,
> 631/666, 383/222, 1667/666, 2185/666, 901/222, 3221/666, 3739/666,
> 473/74, 4775/666, 5293/666, 1937/222, 6329/666, 6847/666, 2455/222,
> 7883/666, 8401/666, 991/74, 9437/666, 9955/666, 3491/222, 10991/666,
> 11509/666, 4009/222, 12545/666, 13063/666, 74/1509, 3743/4527,
> 7264/4527, 3595/1509, 14306/4527, 17827/4527, 2372/503, 24869/4527,
> 28390/4527, 10637/1509, 35432/4527, 38953/4527, 14158/1509, 45995/4527,
> 49516/4527, 5893/503, 56558/4527, 60079/4527, 21200/1509, 67121/4527,
> 70642/4527, 24721/1509, 77684/4527, 81205/4527, 503/9414, 7825/9414,
> 1046/1683, 785/561, 3664/1683, 4973/1683, 698/187, 7591/1683, 8900/1683,
> 3403/561, 11518/1683, 12827/1683, 4712/561, 15445/1683, 16754/1683,
> 187/2007, 1748/2007, 1103/669, 4870/2007, 6431/2007, 223/888, 2741/2664,
> 4813/2664, 296/765, 85/99, 11/18, 25/18, 13/6, 53/18, 67/18, 2/9, 1
>
> Code in sage:
>
> def qsort(A):
> if A == []:
> return []
>
> i = randrange(len(A))
> A_lo = qsort([x for x in (A[:i] + A[i + 1 :]) if x < A[i]])
> A_hi = qsort([x for x in (A[:i] + A[i + 1 :]) if x >= A[i]])
>
> return A_lo + [A[i]] + A_hi
>
> d = 7
> k = 9
> z = d/k
> f = 1
> print f
> S = [[d+k, 1, 1-z]]
> G = []
> h = 0
> while (len(S) > 0) & (not(h == 1)):
> G.append(S[0])
> h = S[0][2]
> del(S[0])
> h1 = 1/h-z
> h2 = h-z
> if (h1 > 0) & (not(([h1.numerator()+h1.denominator(), h, h1] in S) |
> ([h1.numerator()+h1.denominator(), h, h1] in G))):
> S.append([h1.numerator()+h1.denominator(), h, h1])
> if (h2 > 0) & (not(([h2.numerator()+h2.denominator(), h, h2] in S) |
> ([h2.numerator()+h2.denominator(), h, h2] in G))):
> S.append([h2.numerator()+h2.denominator(), h, h2])
> S = qsort(S)
> print
> G = qsort(G)
> LG = len(G)
> if h == 1:
> W = []
> print "Solved!"
> #backtrack
> while not(h == 1-z):
> i = 0
> while not(G[i][2] == h):
> i = i+1
> #print G[i]
> h = G[i][1]
> W.append(G[i][2])
> del(G[i])
> print W
> print "ready"
>
> Matthijs Coster
>
>
> hv at crypt.org schreef op 21-1-2015 om 15:56:
>> When n == 1 (mod m), m/n solves [ n(n-1)/m, (n-1)/m ].
>> 3/(6n+2) solves [ n(6n+2), 2n ].
>> 3/(6n+5) solves [ (4n+3)(6n+5), (n+1)(6n+4), 2n+1 ].
>>
>> That's enough to cover all 1/n, 2/n, 3/n.
>>
>> I suspect that all rationals r < 1 are solvable, and that it should be
>> provable. But I've had no luck with 7/9 yet, either.
>>
>> Hugo
>>
>> Frank Adams-Watters <franktaw at netscape.net> wrote:
>> :1/(N-1) - 1/(N*(N-1)) = 1/N, so take a = N*(N-1), b=N-1.
>> :
>> :Franklin T. Adams-Watters
>> :
>> :-----Original Message-----
>> :From: M. F. Hasler <oeis at hasler.fr>
>> :To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>> :Sent: Tue, Jan 20, 2015 9:38 pm
>> :Subject: [seqfan] Re: Puzzle
>> :
>> :
>> :Hugo makes a good point :
>> :the sequence of operations can be coded as a list of integers (m(k),
>> :k=1..n),
>> :which mean "add m(k) times r, then take the reciprocal"
>> :(the last reciprocal being "useless" if it ends in 1).
>> :
>> :e.g., for r=1/sqrt(2), one has that operations [1,4,1]
>> : yield the values [ 1/(1+r)=2-2r ; 1/(2+2r) = 1-r ; 1 ]
>> :
>> :for r=1/sqrt(3), one has that [1,3,1] yields the
>> : values [ 1/(1+r)=3/2-r*3/2 ; 1/(3/2+r*3/2) = 1-r ; 1 ]
>> :
>> :E.g., for r = 1/N, one has that [N(N-1), N-1] yields
>> : values [ 1/(1+N-1) = 1/N ; 1/(1/N + (N-1)/N) = 1 ]
>> :
>> :(Not any 1/N is of the form (a-b)/ab, though, is it?)
>> :Maximilian
>> :
>> :
>> :> -----Original Message-----
>> :> From: hv <hv at crypt.org>
>> :> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>> :> Sent: Tue, Jan 20, 2015 8:24 pm
>> :> Subject: [seqfan] Re: Puzzle
>> :>
>> :>
>> :> It is never useful to use the reciprocal twice in a row, nor to start
>> :or
>> :> end the sequence with it, so we're talking about a sequence [a, b, c,
>> :... ]
>> :> of additions, with a single reciprocal between each set of additions.
>> :>
>> :> When the sequence is length 1 (ie with no reciprocals), the only
>> :solution
>> :> is r = 0; when the sequence is length 2, we have r = 0 or r = (a - b)
>> :/ ab,
>> :> with a and b any positive integers.
>> :>
>> :> At length 3, we get an ugly quadratic, which simplifies to the same
>> :case
>> :> when a + c = b: abcr^2 + (ab - bc)r + (a + c - b) = 0, if I have it
>> :right.
>> :> I guess it'll only get uglier for longer sequences.
>> :>
>> :> The rationals satisfying (a - b) / ab with a, b in Z+ seem like quite
>> :> an interesting subset of Q to characterize, though.
>> :>
>> :> I'm not sure "no irrational" is correct though, I think for example
>> :> that 1/sqrt(3) works via the sequence [add, rec, add, add, add, rec,
>> :add].
>> :>
>> :> Hugo
>> :
>> :_______________________________________________
>> :
>> :Seqfan Mailing list - http://list.seqfan.eu/
>> :
>> :
>> :
>> :
>> :_______________________________________________
>> :
>> :Seqfan Mailing list - http://list.seqfan.eu/
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list