login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Run lengths in the binary expansion of n are one more than the exponents of corresponding primes in the prime factorization of a(n).
4

%I #16 May 17 2017 17:55:38

%S 1,1,2,2,1,3,4,4,3,1,2,6,5,9,8,8,9,5,6,2,1,3,4,12,15,7,10,18,25,27,16,

%T 16,27,25,18,10,7,15,12,4,3,1,2,6,5,9,8,24,45,35,30,14,11,21,20,36,75,

%U 49,50,54,125,81,32,32,81,125,54,50,49,75,36,20,21,11,14,30,35,45,24,8,9,5,6,2,1,3,4,12,15,7,10,18,25,27,16,48,135,175,90,70

%N Run lengths in the binary expansion of n are one more than the exponents of corresponding primes in the prime factorization of a(n).

%H Antti Karttunen, <a href="/A286468/b286468.txt">Table of n, a(n) for n = 1..65536</a>

%F a(1) = 1; and then after, a(4n) = 2*a(2n), a(4n+1) = A003961(a((n-1)/2)), a(4n+2) = A003961(a(n/2)), a(4n+3) = 2*a((n-1)/2).

%F a(n) = A052126(1+A075157(n)) = A052126(A075159(1+n)).

%F Other identities. For all n >= 1:

%F a(A007283(n)) = A007283(n-1).

%e For n = 25, "11001" in binary, the lengths of runs from the right are 1, 2 and 2, thus we form a product prime(1)^(1-1) * prime(2)^(2-1) * prime(3)^(2-1) = 2^0 * 3^1 * 5^1 = 15, and a(26) = 15.

%o (PARI) A286468(n) = { my(p=((n+1)%2), i=0, m=1); while(n>0, if(((n%2)==p), m *= prime(i), p = (n%2); i = i+1); n = n\2); m };

%o (Scheme)

%o (define (A286468 n) (fold-left (lambda (a r) (* (A003961 a) (A000079 (- r 1)))) 1 (binexp->runcount1list n)))

%o (define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))

%o ;; Or by implementing the given recurrence:

%o (define (A286468 n) (cond ((= 1 n) n) ((zero? (modulo n 4)) (* 2 (A286468 (/ n 2)))) ((= 1 (modulo n 4)) (A003961 (A286468 (/ (- n 1) 2)))) ((= 2 (modulo n 4)) (A003961 (A286468 (/ n 2)))) ((= 3 (modulo n 4)) (* 2 (A286468 (/ (- n 1) 2))))))

%Y Cf. A000079, A003961, A007283, A052126, A075157, A075159.

%Y Cf. A000975 (positions of ones).

%K nonn

%O 1,3

%A _Antti Karttunen_, May 17 2017