login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180835 T(n,k) = number of n-bit binary numbers with every initial substring not divisible by k. 1
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 (list; table; graph; refs; listen; history; text; internal format)
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: A185158 A185700 A061926 * A053188 A109389 A098884

Adjacent sequences:  A180832 A180833 A180834 * A180836 A180837 A180838

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Sep 20 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 18:38 EDT 2022. Contains 354851 sequences. (Running on oeis4.)