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

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

Offset

1,12

Comments

Table starts

.0.1...1....1....1....1....1.....1.....1.....1.....1.....1.....1.....1.....1

.0.1...1....2....2....2....2.....2.....2.....2.....2.....2.....2.....2.....2

.0.1...2....3....3....3....3.....4.....4.....4.....4.....4.....4.....4.....4

.0.1...3....5....5....6....6.....7.....7.....7.....7.....7.....7.....7.....7

.0.1...5....8....9...10...11....13....13....13....14....14....14....14....14

.0.1...8...13...16...19...20....24....24....25....26....26....27....27....27

.0.1..13...21...28...33...37....44....45....47....49....50....51....51....52

.0.1..21...34...49...61...68....81....84....88....93....95....98....99...100

.0.1..34...55...86..108..125...149...157...166...176...181...187...190...193

.0.1..55...89..151..197..230...274...293...313...333...345...358...364...372

.0.1..89..144..265..352..423...504...547...589...631...657...685...701...717

.0.1.144..233..465..638..778...927..1021..1109..1195..1252..1310..1346..1382

.0.1.233..377..816.1145.1431..1705..1906..2089..2263..2385..2507..2585..2664

.0.1.377..610.1432.2069.2632..3136..3558..3934..4286..4544..4796..4969..5135

.0.1.610..987.2513.3721.4841..5768..6642..7408..8117..8657..9176..9545..9898

.0.1.987.1597.4410.6714.8904.10609.12399.13951.15372.16493.17556.18338.19079

Links

R. H. Hardin, Table of n, a(n) for n=1..10000

R. H. Hardin, Empirical recurrences for columns of T(n,k), k=1..99

Prog

(C)
#include <stdio.h>
#define BIG 1000000000000000000LL
#define Q(level, sum, i) (((level)*K+sum)*L+i)
int L, N, K;
unsigned long long *count, *cache, *sv, *mem;
go(level, sum)
{
int i;
if(level&&sum%K==0)return;
if(level==N) {
if(++count[0]<BIG)return;
for(i=1; i<L; i++) {
if(count[i-1]<BIG)return;
count[i-1]-=BIG;
count[i]++;
}
if(count[i-1]>=BIG)fprintf(stderr, "overflow count\n"), exit(1);
return;
}
if(cache[Q(level, sum, 0)]) {
xx:;
for(i=0; i<L; i++) {
if((count[i]+=cache[Q(level, sum, i)])>=BIG) {
count[i]-=BIG;
if(i==L-1)fprintf(stderr, "overflow cache\n"), exit(1);
count[i+1]++;
}
}
return;
}
memcpy(sv+L*level, count, L*sizeof*count);
memset(count, 0, L*sizeof*count);
go(level+1, (sum*2)%K);
go(level+1, (sum*2+1)%K);
memcpy(&cache[Q(level, sum, 0)], count, L*sizeof*count);
memcpy(count, sv+L*level, L*sizeof*count);
goto xx;
}
main()
{
int i, index, need, memsize;
N=0; K=0;
if(!(mem=(unsigned long long*)malloc(memsize=sizeof*mem)))fprintf(stderr, "out of memory1\n"), exit(1);
for(index=1; index<=10000; index++) {
N++;
if(--K<=0) {
K=N;
N=1;
}
L=N/50+1;
need=(N*K*L+(N+1)*L)*sizeof*count;
if(need>memsize) {
if(!(mem=(unsigned long long*)realloc(mem, memsize=need)))fprintf(stderr, "out of memory2\n"), exit(1);
}
count=mem;
sv=mem+L;
cache=sv+N*L;
memset(mem, 0, memsize);
go(0, 0);
printf("%d ", index);
for(i=L-1; i>0; i--)if(count[i])break;
printf("%llu", count[i]);
while(--i>=0)printf("%018llu", count[i]);
printf("\n");
fflush(stdout);
}
exit(0);
}
(Python)
from itertools import product
def d(s, k): return False if k == 0 else int("".join(s), 2)%k == 0
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)))
def auptodiag(maxd): return [T(d+1-j, j) for d in range(1, maxd+1) for j in range(d, 0, -1)]
print(auptodiag(14)) # Michael S. Branicky, Jun 09 2022

Crossrefs

Sequence in context: A185700 A368494 A061926 * A053188 A109389 A098884

Adjacent sequences: A180832 A180833 A180834 * A180836 A180837 A180838

Keyword

nonn,tabl

Author

R. H. Hardin, Sep 20 2010

Status

approved