login
T(n,k) = number of n-bit binary numbers with every initial substring not divisible by k.
1

%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