[seqfan] Initial Substrings of n-bit Binary Numbers Not Divisible by k

[Ron Hardin]

A surprisingly large number of these are in OEIS

T(n,k) = Number of n-bit binary strings with no initial substring
representing a binary number divisible by k

Columns:


A000045
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,
10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169
Number of n-bit binary numbers with every initial substring not divisible by 3
Empirical: a(n)=a(n-1)+a(n-2)

A000045
1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,
17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,
2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986
Number of n-bit binary numbers with every initial substring not divisible by 4
Empirical: a(n)=a(n-1)+a(n-2)

A005314
1,2,3,5,9,16,28,49,86,151,265,465,816,1432,2513,4410,7739,13581,23833,
41824,73396,128801,226030,396655,696081,1221537,2143648,3761840,6601569,
11584946,20330163,35676949,62608681,109870576,192809420,338356945
Number of n-bit binary numbers with every initial substring not divisible by 5
Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-3)

A028495
1,2,3,6,10,19,33,61,108,197,352,638,1145,2069,3721,6714,12087,21794,
39254,70755,127469,229725,413908,745889,1343980,2421850,4363921,7863641,
14169633,25532994,46008619,82904974,149389218,269190547,485064009
Number of n-bit binary numbers with every initial substring not divisible by 6
Empirical: a(n)=a(n-1)+2*a(n-2)-a(n-3)

A001590
1,2,3,6,11,20,37,68,125,230,423,778,1431,2632,4841,8904,16377,30122,
55403,101902,187427,344732,634061,1166220,2145013,3945294,7256527,
13346834,24548655,45152016,83047505,152748176,280947697,516743378
Number of n-bit binary numbers with every initial substring not divisible by 7
Empirical: a(n)=a(n-1)+a(n-2)+a(n-3)

A000073
1,2,4,7,13,24,44,81,149,274,504,927,1705,3136,5768,10609,19513,35890,
66012,121415,223317,410744,755476,1389537,2555757,4700770,8646064,
15902591,29249425,53798080,98950096,181997601,334745777,615693474
Number of n-bit binary numbers with every initial substring not divisible by 8
Empirical: a(n)=a(n-1)+a(n-2)+a(n-3)

A059633
1,2,4,7,13,24,45,84,157,293,547,1021,1906,3558,6642,12399,23146,43208,
80659,150571,281080,524709,979506,1828503,3413377,6371957,11894917,
22204960,41451340,77379720,144449397,269652414,503376448,939683219
Number of n-bit binary numbers with every initial substring not divisible by 9
Empirical: a(n)=2*a(n-1)-a(n-3)+a(n-4)

1,2,4,7,13,25,47,88,166,313,589,1109,2089,3934,7408,13951,26273,49477,
93175,175468,330442,622289,1171897,2206921,4156081,7826746,14739356,
27757207,52272469,98439697,185381983,349112000,657448942,1238110153
Number of n-bit binary numbers with every initial substring not divisible by 10
Empirical: a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)

1,2,4,7,14,26,49,93,176,333,631,1195,2263,4286,8117,15372,29112,55133,
104412,197738,374481,709201,1343102,2543599,4817129,9122795,17276969,
32719540,61965053,117350910,222241980,420887215,797086346,1509541322
Number of n-bit binary numbers with every initial substring not divisible by 11
Empirical: a(n)=2*a(n-1)-a(n-4)+a(n-6)

A052535
1,2,4,7,14,26,50,95,181,345,657,1252,2385,4544,8657,16493,31422,59864,
114051,217286,413966,788674,1502555,2862617,5453761,10390321,19795288,
37713313,71850128,136886433,260791401,496850954,946583628,1803399103
Number of n-bit binary numbers with every initial substring not divisible by 12
Empirical: a(n)=a(n-1)+2*a(n-2)-a(n-4)

1,2,4,7,14,27,51,98,187,358,685,1310,2507,4796,9176,17556,33588,64262,
122947,235225,450038,861022,1647327,3151702,6029906,11536550,22071982,
42228605,80792701,154574383,295735130,565806993,1082514458,2071090611
Number of n-bit binary numbers with every initial substring not divisible by 13
Empirical: a(n)=2*a(n-1)-a(n-4)+a(n-5)-a(n-6)+a(n-7)

1,2,4,7,14,27,51,99,190,364,701,1346,2585,4969,9545,18338,35236,67695,
130062,249891,480107,922427,1772254,3405004,6542005,12569090,24148849,
46396945,89141969,171267522,329054532,632209047,1214656654,2333707243
Number of n-bit binary numbers with every initial substring not divisible by 14
Empirical: a(n)=a(n-1)+a(n-2)+2*a(n-3)-a(n-4)

A001631
1,2,4,7,14,27,52,100,193,372,717,1382,2664,5135,9898,19079,36776,70888,
136641,263384,507689,978602,1886316,3635991,7008598,13509507,26040412,
50194508,96753025,186497452,359485397,692930382,1335666256,2574579487
Number of n-bit binary numbers with every initial substring not divisible by 15
Empirical: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)

A000078
1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536,10671,20569,39648,76424,
147312,283953,547337,1055026,2033628,3919944,7555935,14564533,28074040,
54114452,104308960,201061985,387559437,747044834,1439975216,2775641472
Number of n-bit binary numbers with every initial substring not divisible by 16
Empirical: a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)

1,2,4,8,15,29,56,108,209,404,781,1510,2919,5643,10909,21089,40769,78814,
152362,294544,569408,1100771,2127994,4113806,7952748,15374133,29721043,
57456274,111073606,214725827,415104744,802474257,1551331182,2999010143
Number of n-bit binary numbers with every initial substring not divisible by 17
Empirical: a(n)=2*a(n-1)-a(n-4)+a(n-5)

1,2,4,8,15,29,56,109,211,409,792,1535,2974,5763,11166,21636,41922,81230,
157393,304970,590918,1144981,2218548,4298725,8329335,16139166,31271722,
60593011,117406801,227490877,440793021,854093541,1654916796,3206615524
Number of n-bit binary numbers with every initial substring not divisible by 18
Empirical: a(n)=2*a(n-1)-a(n-3)+2*a(n-4)-a(n-5)

1,2,4,8,15,29,57,110,214,415,806,1564,3036,5894,11441,22209,43112,83689,
162456,315358,612171,1188341,2306797,4477935,8692530,16873865,32755403,
63584511,123429713,239600710,465110864,902869261,1752642143,3402214046
Number of n-bit binary numbers with every initial substring not divisible by 19
Empirical: a(n)=2*a(n-1)-a(n-5)+a(n-7)-a(n-8)+a(n-10)

1,2,4,8,15,29,57,111,215,418,814,1583,3077,5984,11639,22634,44014,85595,
166460,323714,629524,1224240,2380789,4629926,9003829,17509786,34051355,
66219793,128777877,250434842,487021607,947112771,1841853826,3581860218
Number of n-bit binary numbers with every initial substring not divisible by 20
Empirical: a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-5)

0,1,0,1,1,0,1,1,1,0,1,2,2,1,0,1,2,3,3,1,0,1,2,3,5,5,1,0,1,2,3,5,8,8,1,0,
1,2,3,6,9,13,13,1,0,1,2,4,6,10,16,21,21,1,0,1,2,4,7,11,19,28,34,34,1,0,
1,2,4,7,13,20,33,49,55,55,1,0,1,2,4,7,13,24,37,61,86,89,89,1,0,1,2,4,7
T(n,k)=number of n-bit binary numbers with every initial substring not divisible 
by k
Table starts:
.0.1.......1.......1........1........1........1........1........1........1
.0.1.......1.......2........2........2........2........2........2........2
.0.1.......2.......3........3........3........3........4........4........4
.0.1.......3.......5........5........6........6........7........7........7
.0.1.......5.......8........9.......10.......11.......13.......13.......13
.0.1.......8......13.......16.......19.......20.......24.......24.......25
.0.1......13......21.......28.......33.......37.......44.......45.......47
.0.1......21......34.......49.......61.......68.......81.......84.......88
.0.1......34......55.......86......108......125......149......157......166
.0.1......55......89......151......197......230......274......293......313
.0.1......89.....144......265......352......423......504......547......589
.0.1.....144.....233......465......638......778......927.....1021.....1109
.0.1.....233.....377......816.....1145.....1431.....1705.....1906.....2089
.0.1.....377.....610.....1432.....2069.....2632.....3136.....3558.....3934
.0.1.....610.....987.....2513.....3721.....4841.....5768.....6642.....7408
.0.1.....987....1597.....4410.....6714.....8904....10609....12399....13951
.0.1....1597....2584.....7739....12087....16377....19513....23146....26273
.0.1....2584....4181....13581....21794....30122....35890....43208....49477
.0.1....4181....6765....23833....39254....55403....66012....80659....93175
.0.1....6765...10946....41824....70755...101902...121415...150571...175468
.0.1...10946...17711....73396...127469...187427...223317...281080...330442
.0.1...17711...28657...128801...229725...344732...410744...524709...622289
.0.1...28657...46368...226030...413908...634061...755476...979506..1171897
.0.1...46368...75025...396655...745889..1166220..1389537..1828503..2206921
.0.1...75025..121393...696081..1343980..2145013..2555757..3413377..4156081
.0.1..121393..196418..1221537..2421850..3945294..4700770..6371957..7826746
.0.1..196418..317811..2143648..4363921..7256527..8646064.11894917.14739356
.0.1..317811..514229..3761840..7863641.13346834.15902591.22204960.27757207


 rhhardin at mindspring.com
rhhardin at att.net (either)