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

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, 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, 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

Offset: 1

Author

Antti Karttunen, May 17 2017

Keywords

• nonn

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65536

Crossrefs

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

Cf. A000975 (positions of ones).

Programs

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 };

Scheme

(define (A286468 n) (fold-left (lambda (a r) (* (A003961 a) (A000079 (- r 1)))) 1 (binexp->runcount1list n)))
(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)))))))
;; Or by implementing the given recurrence:
(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))))))

Formula

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).

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

Other identities. For all n >= 1:

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