[superprismatic]

We define a sequence of numbers, all less than 1,000,000,000, in

the following way:

We start with the number 123,456,789. If our current number

is N, the next number in the series is

((732,891,011 * floor(N/60)) + 345,678,911) modulo 1,000,000,000

where "floor(x)" is the largest integer less than or equal to x

(in other words, the integer part of x), and

"y modulo 1,000,000,000" is simply the 9 least significant digits

of y (in other words, the remainder after you divide y by

1,000,000,000).

Now, because the numbers in this sequence are all less than

1,000,000,000 , the sequence must eventually fall into a repeating

cycle of numbers. What is the length of this cycle?

Feel free to write a program to compute this. Or even give

a description of the algorithm such a program should use. Try

not to use any large arrays in the program.

[Guest]

You cannot imagine how stupid I feel when someone gives such a task...

[Guest]

the first number that repeats is the 49645th number (including the starting number), It's 655830144, and the pattern is 7087 numbers long.

[bonanova]

First repeating number: 464073344 [11340^th term]

Last repeating number: 470844180 [21796^th term]

Cycle length: 10457

For reference, the first few terms I computed are:

123456789

417495654

551879771

933292867

...

[superprismatic]

First repeating number: 464073344 [11340^th term]

Last repeating number: 470844180 [21796^th term]

Cycle length: 10457

For reference, the first few terms I computed are:

123456789

417495654

551879771

933292867

...

I get the same few terms as you have, but my program

agrees with ksquared's results. I guess we'll have to

wait until more people weigh in to see who's program

is buggy!

[superprismatic]

the first number that repeats is the 49645th number (including the starting number), It's 655830144, and the pattern is 7087 numbers long.

I think you're right because I get the exact same results as you.

Did your algorithm use more than a few hundred bytes of memory

for the variables? I'm more interested in *how* you did it than

I am in the results.

[CaptainEd]

I think you're right because I get the exact same results as you.

Did your algorithm use more than a few hundred bytes of memory

for the variables? I'm more interested in *how* you did it than

I am in the results.

Since you are specifically wanting low-memory approach, here is one:

We want to find how long a cycle you get starting with N=123456789, but using only a few hundred bytes of storage.

That seems to cut out the "obvious" solution--keep an array of all the numbers you ever visit, and look up each new one against the array. Clearly, this would take 50K numbers, according to the folks who have already done it.

A low memory (but high-computing) approach would be:

Function Adv (N)

Adv= ((732,891,011 * floor(N/60)) + 345,678,911) modulo 1,000,000,000

Main routine:

Approach: Establish a candidate first repeated number (MyRepeater), then run 1,000,000,000 times, looking for that candidate. If it's not found in that time, advance the candidate and start again for another 10^9.

MyRepeater = 123456789

Do forever

     MyRepeater = 123456789

     MyLength=1

     For N=Adv(MyRepeater) until MyLength>1,000,000,000 

          if N=MyRepeater, then stop and announce MyRepeater and MyLength

          else N=Adv(N)

     MyRepeater=Adv(MyRepeater)

Edited July 7, 2009 by CaptainEd

[unreality]

there are lots of different ways to program it, but the question seems to imply that you don't have the memory space necessary to fill up an array and check for matches. We can make up for the absence of array memory by having a nested loop... it will only save a couple variables, yet the downside is that it will take many cycles to complete

~~~

first define this: function f(n) = ((732891011 * floor(n/60)) + 345678911) % 1000000000

for simplicity of writing it here, say that D is a constant that stands for 123456789 (I had C but it made ( C ) into a copyright logo © lol)

so then define a variable called "x" as f(D)

LOOP I:

create a loop (LOOP II, nested within LOOP I) that calculates f(n) where n is the previous value in the cycle, starting with f(x) (which is f(f(D)) for the first iteration of LOOP I, but it's kept as "f(x)" since later iterations of LOOP I will have different values of x). Keep a loop counter. Stop when you hit x and exit LOOP I. If you don't hit x and the loop counter exceeds 1 billion, end LOOP II and go back to the start of LOOP I... except this time, redefine "x" as f(y), where y is the x from the previous iteration of LOOP I

by the time LOOP I ends, you should've found the "x" and the "loop counter" variables with which you ended, if it repeats at all. If it doesn't, have a clause following the failed end of LOOP I saying that the cycle did not repeat for some freak reason. Otherwise, you're done! "x" is the sequence member that first repeats and "loop counter" is the count of the cycle

(you may have to subtract 1 from "loop count" depending on how you structured the loop...)

~~~

as you can see, only a couple variables were held at one time. The cost is nested loops so you have order 2 nesting for 1->billion loops and that's pretty time-intensive (that is, you have at maximum 1E9^2 potential loop cycles)

I think that would work (it would need to be tested and debugged of course)

[edit - typo]

edit2 - just curious, is there any mathematical reason you chose the numbers you did? I remember some number-theory concepts from the back of my mind related to multiples of 123456789 and how it flips around in certain ways or something strange like that, but I can't put my finger on it

edit3 - ooh I do remember one thing. If you have 12345679 (ie, no 8) and multiply by 9, the product is 111,111,111 ... not sure if that means anything for this problem, but that leads to some interesting places

Edited July 7, 2009 by unreality

[Guest]

there are lots of different ways to program it, but the question seems to imply that you don't have the memory space necessary to fill up an array and check for matches. We can make up for the absence of array memory by having a nested loop... it will only save a couple variables, yet the downside is that it will take many cycles to complete

~~~

first define this: function f(n) = ((732891011 * floor(n/60)) + 345678911) % 1000000000

for simplicity of writing it here, say that D is a constant that stands for 123456789 (I had C but it made ( C ) into a copyright logo © lol)

so then define a variable called "x" as f(D)

LOOP I:

create a loop (LOOP II, nested within LOOP I) that calculates f(n) where n is the previous value in the cycle, starting with f(x) (which is f(f(D)) for the first iteration of LOOP I, but it's kept as "f(x)" since later iterations of LOOP I will have different values of x). Keep a loop counter. Stop when you hit x and exit LOOP I. If you don't hit x and the loop counter exceeds 1 billion, end LOOP II and go back to the start of LOOP I... except this time, redefine "x" as f(y), where y is the x from the previous iteration of LOOP I

by the time LOOP I ends, you should've found the "x" and the "loop counter" variables with which you ended, if it repeats at all. If it doesn't, have a clause following the failed end of LOOP I saying that the cycle did not repeat for some freak reason. Otherwise, you're done! "x" is the sequence member that first repeats and "loop counter" is the count of the cycle

(you may have to subtract 1 from "loop count" depending on how you structured the loop...)

~~~

as you can see, only a couple variables were held at one time. The cost is nested loops so you have order 2 nesting for 1->billion loops and that's pretty time-intensive (that is, you have at maximum 1E9^2 potential loop cycles)

I think that would work (it would need to be tested and debugged of course)

[edit - typo]

edit2 - just curious, is there any mathematical reason you chose the numbers you did? I remember some number-theory concepts from the back of my mind related to multiples of 123456789 and how it flips around in certain ways or something strange like that, but I can't put my finger on it

edit3 - ooh I do remember one thing. If you have 12345679 (ie, no 8) and multiply by 9, the product is 111,111,111 ... not sure if that means anything for this problem, but that leads to some interesting places

Can we potentially reduce the loops by realizing that as N repeats, so does floor(N/60) ???? I was looking for potential bottom up solutions with respect to this earlier but ran out of time...

[superprismatic]

Can we potentially reduce the loops by realizing that as N repeats, so does floor(N/60) ???? I was looking for potential bottom up solutions with respect to this earlier but ran out of time...

tpaxatb asked why I chose the particular numbers in the puzzle:

I picked 123456789 because it was easy to remember. I chose the other numbers

using a little theory about linear congruential generators and a bit of fiddling

in order to get a relatively small cycle with a rather large tail leading

into it.

By the way, none of the algorithms posted here are general enough to work in

all cases; cycles on the order of trillions would be missed by all of them.

There are ways to detect cycles which use very little space, are quite fast

(i.e., the running time is linear in the length of the cycle), and are

completely general. You can find them out there on the web.

[Guest]

tpaxatb asked why I chose the particular numbers in the puzzle:

I picked 123456789 because it was easy to remember. I chose the other numbers

using a little theory about linear congruential generators and a bit of fiddling

in order to get a relatively small cycle with a rather large tail leading

into it.

By the way, none of the algorithms posted here are general enough to work in

all cases; cycles on the order of trillions would be missed by all of them.

There are ways to detect cycles which use very little space, are quite fast

(i.e., the running time is linear in the length of the cycle), and are

completely general. You can find them out there on the web.

I totally forgot that once the cycle starts it is periodic, and therefore restarts at some multiple of two of where it starts...

[unreality]

tpaxatb asked why I chose the particular numbers in the puzzle:

I picked 123456789 because it was easy to remember. I chose the other numbers

using a little theory about linear congruential generators and a bit of fiddling

in order to get a relatively small cycle with a rather large tail leading

into it.

By the way, none of the algorithms posted here are general enough to work in

all cases; cycles on the order of trillions would be missed by all of them.

There are ways to detect cycles which use very little space, are quite fast

(i.e., the running time is linear in the length of the cycle), and are

completely general. You can find them out there on the web.

I think it was me that asked that, I figured it might have something to do with number theory, but it seems they're more related with computer science, a field which I want to go into but currently don't have that much general knowledge in

[Guest]

After fiddling, I have a program that requires 24 bytes of space and runs in linear time

4 32 bit

2 for the results

2 for tracking temporaries

1 64 bit

to perform the actual math functions (otherwise overflows occur)

[CaptainEd]

tpaxatb asked why I chose the particular numbers in the puzzle:

I picked 123456789 because it was easy to remember. I chose the other numbers

using a little theory about linear congruential generators and a bit of fiddling

in order to get a relatively small cycle with a rather large tail leading

into it.

By the way, none of the algorithms posted here are general enough to work in

all cases; cycles on the order of trillions would be missed by all of them.

There are ways to detect cycles which use very little space, are quite fast

(i.e., the running time is linear in the length of the cycle), and are

completely general. You can find them out there on the web.

Thank you, superprismatic! I took your advice and got a great education--Floyd's and Brent's algorithms, etc., are both new to me.