Qbasicnews.com

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.
11114713151071311611917181**7171615131059152081514117131271313815171413917
2010348151815151291719181919201258162091*717161513105915208151411713127131
38151714139172010348151815151291719181919201258162091*71716151310591520815
141171312713138151714139172010348151815151291719181919201258162091*7171615
13105915208151411713127131381517141391720103481518151512917191819192012581
62091*71716151...




THE CHALLENGE:
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:
11111111191723263235333028293535374544403637363637444340353430252529323031
28312323252929374243433939403842423632342934363640383740353336343030252625
25293842403740322526312427323024273023232628283640394340332937343438444034
34342932343434353130262729323337394236403839384442454338373945454849524647
49504140343019252733323634343129353434343837394445474748475046454338374340
35373634343841363638423641373837423845444135383738414240332928333336403328
32312529353232343429323232302724252731333027293029343942364338423538394542
43423734323128332933343838444038423735354032322728293742444340322628302631
31272530242631262632312631272731322835343131312422192528353744413940363433
35303024232218242832323431292935384245433841343534353131283026263030222422
17222426283534374138384139404033273224263130232424212020171923253032292935
35404033272829364243413633293434373844403740342932343030272425252938403842
41342937353743444034332831273332322631252629363642413837383945504442373431
31273125252835333638423739454542434031...
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
Code:
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...

Code:
'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$
cls
t!=timer
for order= 2 to 15
'print:Print "Now checking order ";order

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



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



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

for i=1 to order
   mid$(a$,i)=chr$(zero+1)
   'print mid$(a$,i,1);
next
sptr=order
do
   nval=0
   for i=sptr-order+1 to sptr
      nval=nval+(asc(mid$(a$,i,1))-zero)
   next
   b$=ltrim$(str$(nval))
   'print b$;
   mid$(a$,sptr+1,len(b$))=b$  
   sptr=sptr+len(b$)
    'print left(a$,sptr)
    rf=repfound (sptr,length,order)
    if rf then exit do
loop until sptr>=ssz-order-4
subseries=rf
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.

ciao,

Mango
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
Period=24405

String fragment at 67925:
73435394543403739384037444236333634333432312627302629373941444440342833312733332832343129353232303021

String fragment at 92330 (67925+24405):
73435394543403739384037444236333634333432312627302629373941444440342833312733332832343129353232303021

These are identical.

---------------------------------

Antoni states:
Starting point=11606
Period=8689

String fragment at 11606:
33333333312526283231323025211925273434394037374037343839404136383836414239403329353836424338413533333

String fragment at 20295 (11606+8689):
33333333327302730273125302326242728364036394237374443374238384140333430211926283133373637364140343227

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!

:king:
Pages: 1 2