%I #9 Jun 09 2022 16:36:17
%S 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,
%T 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,
%U 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
%N T(n,k) = number of n-bit binary numbers with every initial substring not divisible by k.
%C Table starts
%C .0.1...1....1....1....1....1.....1.....1.....1.....1.....1.....1.....1.....1
%C .0.1...1....2....2....2....2.....2.....2.....2.....2.....2.....2.....2.....2
%C .0.1...2....3....3....3....3.....4.....4.....4.....4.....4.....4.....4.....4
%C .0.1...3....5....5....6....6.....7.....7.....7.....7.....7.....7.....7.....7
%C .0.1...5....8....9...10...11....13....13....13....14....14....14....14....14
%C .0.1...8...13...16...19...20....24....24....25....26....26....27....27....27
%C .0.1..13...21...28...33...37....44....45....47....49....50....51....51....52
%C .0.1..21...34...49...61...68....81....84....88....93....95....98....99...100
%C .0.1..34...55...86..108..125...149...157...166...176...181...187...190...193
%C .0.1..55...89..151..197..230...274...293...313...333...345...358...364...372
%C .0.1..89..144..265..352..423...504...547...589...631...657...685...701...717
%C .0.1.144..233..465..638..778...927..1021..1109..1195..1252..1310..1346..1382
%C .0.1.233..377..816.1145.1431..1705..1906..2089..2263..2385..2507..2585..2664
%C .0.1.377..610.1432.2069.2632..3136..3558..3934..4286..4544..4796..4969..5135
%C .0.1.610..987.2513.3721.4841..5768..6642..7408..8117..8657..9176..9545..9898
%C .0.1.987.1597.4410.6714.8904.10609.12399.13951.15372.16493.17556.18338.19079
%H R. H. Hardin, <a href="/A180835/b180835.txt">Table of n, a(n) for n=1..10000</a>
%H R. H. Hardin, <a href="/A180835/a180835.txt">Empirical recurrences for columns of T(n,k), k=1..99</a>
%o (C)
%o #include <stdio.h>
%o #define BIG 1000000000000000000LL
%o #define Q(level,sum,i) (((level)*K+sum)*L+i)
%o int L,N,K;
%o unsigned long long *count,*cache,*sv,*mem;
%o go(level,sum)
%o {
%o int i;
%o if(level&&sum%K==0)return;
%o if(level==N) {
%o if(++count[0]<BIG)return;
%o for(i=1; i<L; i++) {
%o if(count[i-1]<BIG)return;
%o count[i-1]-=BIG;
%o count[i]++;
%o }
%o if(count[i-1]>=BIG)fprintf(stderr,"overflow count\n"),exit(1);
%o return;
%o }
%o if(cache[Q(level,sum,0)]) {
%o xx:;
%o for(i=0; i<L; i++) {
%o if((count[i]+=cache[Q(level,sum,i)])>=BIG) {
%o count[i]-=BIG;
%o if(i==L-1)fprintf(stderr,"overflow cache\n"),exit(1);
%o count[i+1]++;
%o }
%o }
%o return;
%o }
%o memcpy(sv+L*level,count,L*sizeof*count);
%o memset(count,0,L*sizeof*count);
%o go(level+1,(sum*2)%K);
%o go(level+1,(sum*2+1)%K);
%o memcpy(&cache[Q(level,sum,0)],count,L*sizeof*count);
%o memcpy(count,sv+L*level,L*sizeof*count);
%o goto xx;
%o }
%o main()
%o {
%o int i,index,need,memsize;
%o N=0; K=0;
%o if(!(mem=(unsigned long long*)malloc(memsize=sizeof*mem)))fprintf(stderr,"out of memory1\n"),exit(1);
%o for(index=1; index<=10000; index++) {
%o N++;
%o if(--K<=0) {
%o K=N;
%o N=1;
%o }
%o L=N/50+1;
%o need=(N*K*L+(N+1)*L)*sizeof*count;
%o if(need>memsize) {
%o if(!(mem=(unsigned long long*)realloc(mem,memsize=need)))fprintf(stderr,"out of memory2\n"),exit(1);
%o }
%o count=mem;
%o sv=mem+L;
%o cache=sv+N*L;
%o memset(mem,0,memsize);
%o go(0,0);
%o printf("%d ",index);
%o for(i=L-1; i>0; i--)if(count[i])break;
%o printf("%llu",count[i]);
%o while(--i>=0)printf("%018llu",count[i]);
%o printf("\n");
%o fflush(stdout);
%o }
%o exit(0);
%o }
%o (Python)
%o from itertools import product
%o def d(s, k): return False if k == 0 else int("".join(s), 2)%k == 0
%o def T(n, k): return sum(1 for b in (b for b in product("01", repeat=n)) if not any(d(b[:i], k) for i in range(1, n+1)))
%o def auptodiag(maxd): return [T(d+1-j, j) for d in range(1, maxd+1) for j in range(d, 0, -1)]
%o print(auptodiag(14)) # _Michael S. Branicky_, Jun 09 2022
%K nonn,tabl
%O 1,12
%A _R. H. Hardin_, Sep 20 2010