Full Version: Periodic Strings
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2
Here's a challenge that requires a little detective work with number sequences.

Suppose you have a string of two one's (11) and cause the string to grow by application of a simple rule: Add the rightmost two digits of the string, and append the sum to the end of the string. Continue this process and you make the string as long as you like. For example, the first few iterations are 11, 112, 1123, 11235, 112358, 11235813, 112358134, etc. Soon it looks like this:1123581347*1123581347*1123581347*1123581347*1123...
The asterisks show that the string is periodic from the beginning with a repeat or period of 10 digits.

Now if you start with three one's (111) and append the sum of the rightmost 3 digits you get:111359171715139131371191*111359171715139131371191*111359171715139131371191*11135917171513...
This string is also periodic from the beginning, this time with a period of 24.

When you use four one's (1111) as the starting string, a curious thing happens. The string does not become periodic until position 26 (shown by **) and has a period of 86.

Find the starting point and period length for string lengths 5 (11111) through 12 (111111111111).

The 9 length string appears to be a particularly tough one. I could not find any periodicity in this sequence. I looked far enough to get "out of string space" errors in my QBasic application. It seems unlikely, however, that such a simple rule would create a sequence that doesn't eventually result in some pattern. Here are the first 1000 digits of the 9-string:
My results: The program fails with the trivial case of order 11, where all the figures in the series are ones, the result should be period 1 starting at 1
Result for order  2 : Periodicity starts at      1 period is    10

Result for order  3 : Periodicity starts at      1 period is    24

Result for order  4 : Periodicity starts at     26 period is    86

Result for order  5 : Periodicity starts at     41 period is   323

Result for order  6 : Periodicity starts at      1 period is     7

Result for order  7 : Periodicity starts at    455 period is   916

Result for order  8 : Periodicity starts at    328 period is   156

Result for order  9 : Periodicity starts at 11,606 period is  8689

Result for order 10 : Periodicity starts at     22 period is   624

Result for order 11 : Periodicity starts at      1 period is     2

Result for order 12 : Periodicity starts at     31 period is  4368

No periodicity found at order  13  with a buffer of size  32700

No periodicity found at order  14  with a buffer of size  32700

Result for order 15 : Periodicity starts at 13,751 period is 13840
results found in  17.2002  seconds

QB's strings seem to be enough for order 9, but are too short for order 13 and 14

the source for QB: uncommenting the right prints you can make it print the series...
My code checks if the last N figures in the string are found somewhere else
in the already genereted part. N is the order of the series. If N figures are duplicated somewhere, the figures following them are certainly the same...

'Entry series periodicity challenge in QBN
'Antoni Gual October 21 2005
declare function subseries%(order%,length%)
declare function repfound%(sptr%,length%,order%)
defint a-z
const zero= 48
const ssz=32700  'maximum string size in QB!!!!
dim shared a$
a$= space$(ssz)
dim res,order,length,aa$
for order= 2 to 15
'print:Print "Now checking order ";order

res= subseries(order,length)
if  res=0 then
   print "No periodicity found at order ";order;" with a buffer of size ";ssz
   print using "Result for order ## : Periodicity starts at #####, period is ##### "; order;res;length
   'print aa$
   'print mid$(a$,res,length)
end if
print "results found in ";timer-t!;" seconds"

function repfound(sptr,length,order)
  dim b$,p
  'print left$(a$,sptr),b$,p,sptr
  if (p>0) and p<(sptr-order+1) then length=sptr-p-order+1 else p=0
end function

function subseries(order,length)
dim i,b$,sptr,rf,nval

for i=1 to order
   'print mid$(a$,i,1);
   for i=sptr-order+1 to sptr
   'print b$;
    'print left(a$,sptr)
    rf=repfound (sptr,length,order)
    if rf then exit do
loop until sptr>=ssz-order-4
end function

EDITED: Freebasic, with a buffer of 3,7 Mchars, says order 13 has a period of 115552, starting at position 5712...
Quote:Result for order 2 : Periodicity starts at 1 period is 10

Result for order 3 : Periodicity starts at 1 period is 24

Result for order 4 : Periodicity starts at 26 period is 86

Result for order 5 : Periodicity starts at 41 period is 323

Result for order 6 : Periodicity starts at 1 period is 7

Result for order 7 : Periodicity starts at 455 period is 916

Result for order 8 : Periodicity starts at 328 period is 156

Result for order 9 : Periodicity starts at 11,606 period is 8689

Result for order 10 : Periodicity starts at 22 period is 624

Result for order 11 : Periodicity starts at 1 period is 2

Result for order 12 : Periodicity starts at 31 period is 4368

No periodicity found at order 13 with a buffer of size 32700

No periodicity found at order 14 with a buffer of size 32700

Result for order 15 : Periodicity starts at 13,751 period is 13840
results found in 17.2002 seconds

Hats off to Antoni!

So beautifully (and quickly!) done.
Hi Antoni,

to enter your challenge is it a requirement to use strings? it seems like a char array (c++) would be the obvious container as a qb string is pretty limited. it's a nice, easy to concieve, implementable programming challenge. do you *need* the answers, or are you just interested in the challenge? I've worked 44 hrs this week mon-thurs and am too tired to write the code tonight (it'd be c++, not qb since c++ would be easier since we don't know the upper bound of the answer). Have another work day in 8 hrs...sucks...anyway...nice challenge. I'll look, with interest, at the outcome, and may code an answer next week.


First of all, get some rest...it's not my challenge, it's whodat´s Big Grin

However, it would be a good challenge to implement it using an arrray and a smart searching algorithm... FB needed 1 minute to scan the case of order 24.
I get all the same numbers as you except

Order 9 I get a period of 24405 starting at 67925

I can't do 13 yet because some of the additions are over 99.
Quote:Order 9 I get a period of 24405 starting at 67925

I believe Quibbler may have the right answer to order 9.

Quibbler states:
Starting point= 67925

String fragment at 67925:

String fragment at 92330 (67925+24405):

These are identical.


Antoni states:
Starting point=11606

String fragment at 11606:

String fragment at 20295 (11606+8689):

These do not match.
Nice challange. I would not have believed that a periodicity of several thousand was possible, but it is. For anybody who is interested the answer for 13 is

period 115552 starting at 5712.

The trick in qbasic is to dump the numbers on disk then search for sequences. oh and don't use strings - too slow.
23 is the biggest i've found with a period of 547811 starting at 79805.
I know this is getting obsessive - this is my last one honestly

for 31 the period is 5,506,975 and it starts at 4,160,374
Quote:I know this is getting obsessive - this is my last one honestly

for 31 the period is 5,506,975 and it starts at 4,160,374

...and to think I started this with a pad and pencil!

Pages: 1 2