A075157 - OEIS

A075157

Run lengths in the binary expansion of n gives the vector of exponents in prime factorization of a(n)+1, with the least significant run corresponding to the exponent of the least prime, 2; with one subtracted from each run length, except for the most significant run of 1's.

0, 1, 2, 3, 5, 4, 8, 7, 11, 14, 6, 9, 17, 24, 26, 15, 23, 44, 34, 29, 13, 10, 20, 19, 35, 74, 48, 49, 53, 124, 80, 31, 47, 134, 174, 89, 69, 76, 104, 59, 27, 32, 12, 21, 41, 54, 62, 39, 71, 224, 244, 149, 97, 120, 146, 99, 107, 374, 342, 249, 161, 624, 242, 63, 95, 404

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

To make this a permutation of nonnegative integers, we subtract one from each run count except for the most significant run, e.g. a(11) = 9, as 11 = 1011 and 9+1 = 10 = 5^1 * 3^(1-1) * 2^(2-1).

LINKS

Paul Tek (terms 0..10000) & Antti Karttunen, Table of n, a(n) for n = 0..16384

Index entries for sequences that are permutations of the natural numbers

FORMULA

a(n) = A075159(n+1) - 1.

a(0) = 0; for n >= 1, a(n) = (A000040(A005811(n)) * A286468(n)) - 1.

Other identities. For all n >= 1:

a(A000975(n)) = A006093(n) = A000040(n)-1.

PROG

(Haskell)

import Data.List (group)

a075157 0 = 0

a075157 n = product (zipWith (^) a000040_list rs') - 1 where

rs' = reverse $ r : map (subtract 1) rs

(r:rs) = reverse $ map length $ group $ a030308_row n

-- Reinhard Zumkeller, Aug 04 2014

(PARI)

A005811(n) = hammingweight(bitxor(n, n>>1)); \\ This function from Gheorghe Coserea, Sep 03 2015

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

A075157(n) = if(!n, n, (prime(A005811(n))*A286468(n))-1);

(Scheme)

(define (A075157 n) (if (zero? n) n (+ -1 (* (A000040 (A005811 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, using the code of A286468:

(define (A075157 n) (if (zero? n) n (- (* (A000040 (A005811 n)) (A286468 n)) 1)))

CROSSREFS

Inverse of A075158.

Cf. A008578, A056539, A059900, A075162.

Cf. A000040, A000975, A006093, A030308, A007088, A075159, A278217, A286617.

Sequence in context: A288119 A292575 A096070 * A183080 A183082 A183209

Adjacent sequences: A075154 A075155 A075156 * A075158 A075159 A075160

KEYWORD

nonn

AUTHOR

Antti Karttunen, Sep 13 2002

EXTENSIONS

Entry revised, PARI-program added and the old incorrect Scheme-program replaced with a new one by Antti Karttunen, May 17 2017

STATUS

approved