## Tuesday, April 8, 2014

### rough notes on finding near misses to cycles in juggler sequence

this is about feeding a number back into a function over and over again, and seeing what kind of patterns we get.

see the entry for the collatz conjecture in the complexity lab manual, it is a similar game

def jug(n) = {int(sqrt(n^3))  if n is odd else  int(sqrt(n))}

int(r) is the greatest integer less than r, i.e. int(4.773)=4

so that jug(2)=2, and jug(2)=1 and jug(1)=1 and we stop there.  that's a fixed point.

jug(3)=int(sqrt(27))=5, and jug(5)=11, etc..

the sequence of numbers we get is called the orbit of the first number under the dynamical system for our function jug(x)

here are the orbits for the first 9 integers
[1]
[2, 1]
[3, 5, 11, 36, 6, 2, 1]
[4, 2, 1]
[5, 11, 36, 6, 2, 1]
[6, 2, 1]
[7, 18, 4, 2, 1]
[8, 2, 1]
[9, 27, 140, 11, 36, 6, 2, 1]
>>>

here is orbit for 37:

[37, 225, 3375, 196069, 86818724, 9317, 899319, 852846071, 24906114455136, 4990602, 2233, 105519, 34276462, 5854, 76, 8, 2, 1]

it seems that no matter what n we start off with we reach 1 (i think this has been tested up to a million)

no one knows how to prove that this is so.  There are many systems like this and they puzzle us.
wiki on the juggler sequence

the question is: are there numbers for which the orbit reaches a fixed point?  or are there numbers for which the orbit cycles?  for instance, look at the orbit for 3:
[3, 5, 11, 36, 6, 2, 1]
if the square root of 36 had happened to be 5 this orbit would have been:
3, 5, 11, 36, 5, 11, 36, 5...

and 5,11,36 would be a cycle.  no one has found any cycles yet, but lets look for almost cycles like 3, 5, 11, 36, 6... 6 is CLOSE to 5.

so,

i generate an orbit under this dynamical system.  [(x0,0), (x1,1)....(xn,n)]
then i sort this by x, so that xi that are near each other in size are near each other in the sequence

then i create a sequence of the differences between consecutive xi's  and sort that.  here is what i get for 37:

(diff, (xi, i), (xj, j))
(1L, (1L, 17), (2L, 16))
(6L, (2L, 16), (8L, 15))
(9L, (8L, 15), (17, 18))
(20, (17, 18), (37, 0))
(39L, (37, 0), (76L, 14))
(149L, (76L, 14), (225, 1))
(1142L, (2233L, 10), (3375, 2))
(2008L, (225, 1), (2233L, 10))
(2479L, (3375, 2), (5854L, 13))
(3463L, (5854L, 13), (9317, 5))
(90550L, (105519L, 11), (196069, 3))
(96202L, (9317, 5), (105519L, 11))
(703250, (196069, 3), (899319, 6))
(4091283L, (899319, 6), (4990602L, 9))
(29285860L, (4990602L, 9), (34276462L, 12))
(52542262L, (34276462L, 12), (86818724, 4))
(766027347, (86818724, 4), (852846071, 7))
(24905261609065L, (852846071, 7), (24906114455136L, 8))

now if i want to search for orbits with near misses... what do i search for?  obviously the first few entries do not count

the 4th and 5th entries are close to what i'm looking for.  how do i write an algorithm to pick them out?  the diff must be small but the indexes must be far apart.

the 3rd entry has indices 3 apart but i'm not going to count that as a good candidate!

hmm... a programming puzzle!

this post is continued in the comments...

barry goldman said...

we can also look at consecutive runs of even numbers or consecutive runs of odd numbers

barry goldman said...

well, the only near misses i find up to n=11228 are

(2, 3), (5, 6),
orbit is:
[3, 5, 11, 36, 6, 2, 1])

(10, 11)
orbit is
[10, 3, 5, 11, 36, 6, 2, 1])

(12, 11)
orbit is:
[12, 3, 5, 11, 36, 6, 2, 1])

plenty of orbits hit these 4 pairs

barry goldman said...

next i should look for further misses, i.e. ones that are 2 apart 3 apart and so on...

barry goldman said...

ok, here are the 100 closest near misses for orbits starting with n up to 15343
((diff betw xi,xj), xi, xj, (diff betw i,j))
(1, 2, 3, 5)
(1, 5, 6, 3)
(1, 10, 11, 3)
(1, 11, 12, 3)
(2, 9, 11, 3)
(2, 34, 36, 3)
(3, 2, 5, 4)
(3, 4, 7, 2)
(3, 6, 9, 5)
(3, 11, 14, 3)
(3, 15, 18, 3)
(3, 36, 39, 11)
(4, 6, 10, 5)
(4, 32, 36, 3)
(5, 6, 11, 2)
(5, 135, 140, 11)
(6, 21, 27, 3)
(6, 30, 36, 3)
(7, 6, 13, 2)
(7, 18, 25, 8)
(7, 29, 36, 6)
(8, 7, 15, 2)
(8, 11, 19, 5)
(8, 19, 27, 3)
(8, 28, 36, 3)
(9, 8, 17, 2)
(9, 27, 36, 3)
(10, 11, 21, 5)
(10, 26, 36, 3)
(12, 11, 23, 5)
(13, 23, 36, 6)
(13, 36, 49, 8)
(13, 46, 59, 8)
(14L, 1383, 1397L, 19)
(15, 11, 26, 2)
(15, 18, 33, 5)
(15, 31, 46, 3)
(15, 36, 51, 8)
(16, 11, 27, 2)
(17, 11, 28, 2)
(17, 12, 29, 2)
(17, 18, 35, 5)
(17, 33, 50, 3)
(17, 36, 53, 8)
(18, 13, 31, 2)
(19, 11, 30, 2)
(19, 35, 54, 3)
(19, 36, 55, 8)
(19, 70, 89, 8)
(19, 77, 96, 11)
(20L, 265, 285L, 19)
(21, 11, 32, 2)
(21, 78, 99, 8)
(22, 14, 36, 4)
(23, 11, 34, 2)
(23, 47, 70, 3)
(23, 82, 105, 8)
(23L, 140L, 163, 38)
(24, 12, 36, 4)
(25, 16, 41, 2)
(25, 36, 61, 8)
(25, 43, 68, 3)
(25, 86, 111, 8)
(27, 45, 72, 3)
(27, 70, 97, 8)
(27, 82, 109, 8)
(27L, 455, 482L, 19)
(29L, 8L, 37, 15)
(29L, 100L, 129, 8)
(29, 111, 140, 11)
(30, 17, 47, 2)
(30, 49, 79, 3)
(31, 36, 67, 8)
(31, 51, 82, 3)
(31, 109, 140, 11)
(32, 18, 50, 2)
(33, 25, 58, 6)
(33, 36, 69, 11)
(33, 53, 86, 3)
(33L, 140L, 173, 27)
(33L, 467, 500L, 19)
(34, 18, 52, 2)
(35, 8, 43, 4)
(35, 55, 90, 3)
(35, 61, 96, 3)
(35, 105, 140, 11)
(35, 140, 175, 19)
(36, 18, 54, 2)
(37, 8, 45, 4)
(37, 20, 57, 2)
(37, 36, 73, 5)
(37, 38, 75, 5)
(38, 18, 56, 2)
(39L, 37, 76L, 14)
(39, 96, 135, 8)
(40, 18, 58, 2)
(40L, 253L, 293, 46)
(41, 22, 63, 2)
(41, 36, 77, 16)
(41L, 115, 156L, 11)
>>>
i could list some of the interesting orbits.

next i need to make my algorithsms MUCH more efficient

barry goldman said...

some interesting orbits that rise far and ALMOST come back to cycle

(3, 36, 39, 11)
[39, 243, 3787, 233046, 482, 21, 96, 9, 27, 140, 11, 36, 6, 2, 1]
>>>

(5, 135, 140, 11)
[135, 1568, 39, 243, 3787, 233046, 482, 21, 96, 9, 27, 140, 11, 36, 6, 2, 1]

(14L, 1383, 1397L, 19)
[1383, 51431, 11663729, 39834202863L, 7950312435856233L, 708885828261354590707939L, 596848959815705913074733623807767972L, 772560004022798162L, 878953925L, 26058485111298L, 5104751L, 11533519236L, 107394L, 327L, 5913L, 454686L, 674L, 25L, 125L, 1397L, 52214L, 228L, 15L, 58L, 7L, 18L, 4L, 2L, 1L]

(20L, 265, 285L, 19)
[265, 4313, 283249, 150748353, 1850882562751L, 2518072881535150900L, 1586843685L, 63212246036575L, 502576100966477058449L, 11266856139354538126112233863522L, 3356613790616152L, 57936290L, 7611L, 663991L, 541057335L, 12585339444404L, 3547582L, 1883L, 81710L, 285L, 4811L, 333697L, 192765120L, 13883L, 1635780L, 1278L, 35L, 207L, 2978L, 54L, 7L, 18L, 4L, 2L, 1L]
>>>

(23L, 140L, 163, 38)
[163, 2081, 94931, 29249071, 158186025767L, 62914706160224995L, 15780772497304229543894404L, 3972502044971L, 7917648073559565948L, 2813831564L, 53045L, 12217059L, 42702176063L, 8824193242915618L, 93937177L, 910450328488L, 954175L, 932056094L, 30529L, 5334194L, 2309L, 110952L, 333L, 6076L, 77L, 675L, 17537L, 2322378L, 1523L, 59436L, 243L, 3787L, 233046L, 482L, 21L, 96L, 9L, 27L, 140L, 11L, 36L, 6L, 2L, 1L]

(40L, 253L, 293, 46)
[293, 5015, 355145, 211645265, 3079022305557L, 5402804496718696385L, 12558242903021082448316336897L, 1407321486798770675765074179033988366542583L, 1669513663420744235279182024159108504608540288637713201172547862L, 40859682615271796005654168626860L, 6392157899744952L, 79950971L, 714884060533L, 604440311668070777L, 469926710892465998765667901L, 10186973980607150314154161189317061176339L, 1028176788659727974283760939823852763403205896125130273562908L, 1013990526908278356763853712011L, 1021059020668217360873509844596641219675498784L, 31954014155786708621395L, 5711999159692334114627669231969031L, 431700152742616744121648934225742169217296804905211L, 8969604696451963404959159520681986480299254693727937813922515065083107921415L, 849493294715904100645426218839627679979244320752168280335076076357225084724916351091795416083100019961902690869963L, 782960644528031182478778269971671893857290991978652977413980144809602271665761768285250254182147217823074414682446735642976716076853608380272794108384550040642846923889122L, 27981433925516240106403191882243981800891079296595365049468474965382471424405323468430L, 5289748002080651110608112412743405750837524L, 2299945217191194558694L, 47957744079L, 10502389448104139L, 1076297119675671654979220L, 1037447405739L, 1056693737376517423L, 1086234770006668118654010684L, 32958075945155L, 189209429057184278800L, 13755341837L, 1613270087556264L, 40165533L, 254554220308L, 504533L, 358372244L, 18930L, 137L, 1603L, 64180L, 253L, 4024L, 63L, 500L, 22L, 4L, 2L, 1L]

biggest entry has 171 digits
>>>