A075158 Prime factorization of n+1 encoded with the run lengths of binary expansion.

0, 1, 2, 3, 5, 4, 10, 7, 6, 11, 21, 8, 42, 20, 9, 15, 85, 12, 170, 23, 22, 43, 341, 16, 13, 84, 14, 40, 682, 19, 1365, 31, 41, 171, 18, 24, 2730, 340, 86, 47, 5461, 44, 10922, 87, 17, 683, 21845, 32, 26, 27, 169, 168, 43690, 28, 45, 80, 342, 1364, 87381, 39, 174762

Offset: 0

Author

Antti Karttunen, Sep 13 2002

Keywords

• nonn

Comments

a(2n) = 1 or 2 mod 4 and a(2n+1) = 0 or 3 mod 4 for all n > 1

Examples

			a(1) = 1 as 2 = 2^1, a(2) = 2 (10 in binary) as 3 = 3^1 * 2^0, a(3) = 3 (11) as 4 = 2^2, a(4) = 5 (101) as 5 = 5^1 * 3^0 * 2^0, a(5) = 4 (100) as 6 = 3^1 * 2^1, a(8) = 6 (110) as 9 = 3^2 * 2^0, a(11) = 8 (1000) as 12 = 3^1 * 2^2, a(89) = 35 (100011) as 90 = 5^1 * 3^2 * 2^1, a(90) = 90 (1011010) as 91 = 13^1 * 11^0 * 7^1 * 5^0 * 3^0 * 2^0.
The binary expansion of a(n) begins from the left with as many 1's as is the exponent of the largest prime present in the factorization of n+1 and from then on follows runs of ej+1 zeros and ones alternatively, where ej are the corresponding exponents of the successively lesser primes (0 if that prime does not divide n+1).
		

Links

• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse of A075157. a(n) = A075160(n+1)-1. a(A006093(n)) = A000975(n). Cf. A059884.

Programs

Haskell

import Data.List (elemIndex); import Data.Maybe (fromJust)
a075158 = fromJust . (`elemIndex` a075157_list)
-- Reinhard Zumkeller, Aug 04 2014