In the sequence 1, 0, 1, 0, 1, 0, 3, 5... each member after the sixth one equals the units' digit of the sum of the six preceding numbers of the sequence.

Prove that the subsequence 0, 1, 0, 1, 0, 1, will never occur.

There is a cycle of 1456 beginning immediately (i.e., 1, 0, 1, 0, 1, 0 starts again at 1457 in the sequence). During this cycle, 0, 1, 0, 1, 0, 1 does not occur, and so will never occur.

10101035098507987674138927095258987967638992783875890765525030558121293858587143
81411838561145292356725831658145929094372501839674769927030134121233234721969410
99256125105472974327253210343347456956567879292765101030598507437674183927090758
98741763894778387039076507503050312129835858769381416338561695292301725836158145
47909432750183417476947703018912123873472141941094756125655472929327258710343897
45690156787479276565103054350743217418347709070398741213894723387034576507053050
36712983035876983141638356169079230127583610314547459432705183412976947253018967
12387897214149109470112565097292987725876534389295690101787474776565653054305743
21291834725907034374121839472383703452150705855036767983030376983691638301169074
73012703361036954745493270563341292194725851896767387892714149659470167565092792
98727587658938929019010123747472156565855430529321296334725457034329121834972383
25345210570585053676743303032198369613830161907478512703811036909745498770563891
29214972585639676783789276914965497016701509274798727037658983929014510123297472
10156585093052987129638972545253432967183492738325895210525585058176743853032143
36961833016145747856770381653690929549872556389679214927585634176783239276969965
49251670105927474372703215898347901456512329297210101585098552987679638927545258
93296763349278332589071052503505812174385853214381961838516145297856725381658190
92909987250138967471492703563412178323477696941549256170105477474327703210398347
45145656732929271010103

 

I tried to see if there was some insight that I overlooked, by running backwards. The 101010 at the beginning of the below sequence is the 010101 terminal sequence sought, backward. The 9 following it is the 9 that would have to precede it in order to produce it. But this reverse sequence also repeats on a cycle of 1456: we're back to 0,1,0,1,0,1 having originated in  0,1,0,1,0,1 and gone through a cycle of 3,6,1,2,3,..., returning again to 0,1,0,1,0,1 without running into a 1,0,1,0,1,0 with which to start off a sequence, so this method is no less laborious than the forward direction from the given starting sequence.

10101099292989565670174783231098149987474976101455692765725254978983459078563149
27097452385169432712921253650381945634796705013830525387098136387459036163169610
91236983349278354529873696769923852954329613216365101094792989015670129783236598
14943747492110145019276527525492398345457856369927092952385619432767921258150381
49563474170501833052583709818138745453616361961096736983899278309529878196769473
85290932961871636565109474798901017012923323654314943297492165145014776527075492
34334545235636947709290738561493276747125810538149013474125501838552583259818183
74545811636141109678198389477830907987814176947835290987961876136565659474743901
01251292387365436994329299216569501472152707099234389545230136947259290783561498
77674767581058314901897412505183850758325431818329545816136141659678143389472330
90743781412194783079098741187618156565497474345101256792387815436949329294716569
05147210770709473438909523018194725479078301149872174767031058369901892912505633
85070332543631832909581618114165417814383947238590743231412149783074598741637618
10156549297434565125674738781093694987929476156905697210725709478938909073018149
72547457830169987212976703655836945189296750563835070387543636332909031618169165
41231438349723854574323691214923307454374163211810101549292934565675674783781098
19498747947610190569271072525947898390907851814927547452330169437212921703650336
94563929670556383057038709363638790903611816961541236938349273854529323696714923
85745432916321631010109

For the forward:

a = 1: b = 0
c = 1: e = 0
e = 1: f = 0
CLS
cutpt = 2000
DO
 g = (a + b + c + d + e + f) MOD 10
 a = b: b = c: c = d: d = e: e = f: f = g: PRINT g;
 ct = ct + 1
 IF a = asv AND b = bsv AND c = csv AND d = dsv AND e = esv AND f = fsv THEN
      GOTO foundDup
 END IF
 IF a = 0 AND b = 1 AND c = 0 AND d = 1 AND e = 0 AND f = 1 THEN
      PRINT "hit "; ct: END
 END IF
 IF ct = cutpt THEN
   asv = a: bsv = b: csv = c: dsv = d: esv = e: fsv = f
 END IF
LOOP

foundDup:

cycLength = ct - cutpt

REDIM hist(cycLength + 1, 6)

a = 1: b = 0
c = 1: d = 0
e = 1: f = 0
CLS
ct = 0
PRINT LTRIM$(STR$(a));
PRINT LTRIM$(STR$(b));
PRINT LTRIM$(STR$(c));
PRINT LTRIM$(STR$(d));
PRINT LTRIM$(STR$(e));
PRINT LTRIM$(STR$(f));
DO
 g = (a + b + c + d + e + f) MOD 10
 a = b: b = c: c = d: d = e: e = f: f = g: PRINT LTRIM$(STR$(g));
 ct = ct + 1
 FOR i = 1 TO cycLength
   FOR j = 1 TO 6
     hist(i, j) = hist(i + 1, j)
   NEXT
 NEXT
 hist(cycLength + 1, 1) = a
 hist(cycLength + 1, 2) = b
 hist(cycLength + 1, 3) = c
 hist(cycLength + 1, 4) = d
 hist(cycLength + 1, 5) = e
 hist(cycLength + 1, 6) = f
 good = 1
 FOR i = 1 TO 6
   IF hist(1, i) <> hist(cycLength + 1, i) THEN good = 0: EXIT FOR
 NEXT
 IF ct > 32 THEN

 END IF
 IF good THEN
  PRINT
  PRINT "cycle "; ct - cycLength; ct
  FOR i = 1 TO 6
    PRINT hist(1, i);
  NEXT
  PRINT
  FOR i = 1 TO 6
    PRINT hist(1 + cycLength, i);
  NEXT
  PRINT
  END
 END IF
 IF a = 0 AND b = 1 AND c = 0 AND d = 1 AND e = 0 AND f = 1 THEN
      PRINT "hit "; ct: END
 END IF
LOOP

 

For the reverse:

a = 1: b = 0
c = 1: e = 0
e = 1: f = 0
CLS
cutpt = 2000
DO
 g = (a - (b + c + d + e + f) + 100) MOD 10
 a = b: b = c: c = d: d = e: e = f: f = g: PRINT g;
 ct = ct + 1
 IF a = asv AND b = bsv AND c = csv AND d = dsv AND e = esv AND f = fsv THEN
      GOTO foundDup
 END IF
 IF a = 0 AND b = 1 AND c = 0 AND d = 1 AND e = 0 AND f = 1 THEN
      PRINT "hit "; ct: END
 END IF
 IF ct = cutpt THEN
   asv = a: bsv = b: csv = c: dsv = d: esv = e: fsv = f
 END IF
LOOP

foundDup:

cycLength = ct - cutpt

REDIM hist(cycLength + 1, 6)

a = 1: b = 0
c = 1: d = 0
e = 1: f = 0
CLS
ct = 0
PRINT LTRIM$(STR$(a));
PRINT LTRIM$(STR$(b));
PRINT LTRIM$(STR$(c));
PRINT LTRIM$(STR$(d));
PRINT LTRIM$(STR$(e));
PRINT LTRIM$(STR$(f));
DO
 g = (a - (b + c + d + e + f) + 100) MOD 10
 a = b: b = c: c = d: d = e: e = f: f = g: PRINT LTRIM$(STR$(g));
 ct = ct + 1
 FOR i = 1 TO cycLength
   FOR j = 1 TO 6
     hist(i, j) = hist(i + 1, j)
   NEXT
 NEXT
 hist(cycLength + 1, 1) = a
 hist(cycLength + 1, 2) = b
 hist(cycLength + 1, 3) = c
 hist(cycLength + 1, 4) = d
 hist(cycLength + 1, 5) = e
 hist(cycLength + 1, 6) = f
 good = 1
 FOR i = 1 TO 6
   IF hist(1, i) <> hist(cycLength + 1, i) THEN good = 0: EXIT FOR
 NEXT
 IF ct > 32 THEN

 END IF
 IF good THEN
  PRINT
  PRINT "cycle "; ct - cycLength; ct
  FOR i = 1 TO 6
    PRINT hist(1, i);
  NEXT
  PRINT
  FOR i = 1 TO 6
    PRINT hist(1 + cycLength, i);
  NEXT
  PRINT
  END
 END IF
 IF a = 0 AND b = 1 AND c = 0 AND d = 1 AND e = 0 AND f = 1 THEN
      PRINT "hit "; ct: END
 END IF
LOOP

The first part of each of these programs looks for a repeat of the 2000th element in the sequence. So long as the repeating cycle begins by the 2000th element, this will find the cycle length.  Then the second phase starts again from the beginning, keeping track of a full cycle-length of sequence members, and checking one cycle-length back for a repetition.

In both cases, the repetition cycle was found to have begun at the very beginning of the sequence.

Posted by Charlie on 2007-03-30 14:44:01