A156552 Unary-encoded compressed factorization of natural numbers.
0, 1, 2, 3, 4, 5, 8, 7, 6, 9, 16, 11, 32, 17, 10, 15, 64, 13, 128, 19, 18, 33, 256, 23, 12, 65, 14, 35, 512, 21, 1024, 31, 34, 129, 20, 27, 2048, 257, 66, 39, 4096, 37, 8192, 67, 22, 513, 16384, 47, 24, 25, 130, 131, 32768, 29, 36, 71, 258, 1025, 65536, 43, 131072, 2049, 38, 63, 68, 69, 262144
Offset: 1
Examples
For 84 = 2*2*3*7 -> 1*1 + 1*2 + 2*4 + 8*8 = 75. For 105 = 3*5*7 -> 2*1 + 4*2 + 8*4 = 42. For 137 = p_33 -> 2^32 = 4294967296. For 420 = 2*2*3*5*7 -> 1*1 + 1*2 + 2*4 + 4*8 + 8*16 = 171. For 147 = 3*7*7 = p_2 * p_4 * p_4 -> 2*1 + 8*2 + 8*4 = 50.
Links
- David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1024 terms from Antti Karttunen)
- Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]
- A puzzle by Sergey Orlov (in Russian)
- Index entries for sequences related to binary expansion of n
- Index entries for sequences that are permutations of the natural numbers
- Index entries for sequences computed from indices in prime factorization
Crossrefs
One less than A005941.
Inverse permutation: A005940 with starting offset 0 instead of 1.
Cf. A000079, A000120, A001222, A052126, A054429, A061395, A064216, A064989, A003188, A243071, A243065-A243066, A244153, A243354, A112798, A125106, A056239, A161511.
Programs
-
Mathematica
Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[ Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ n]], {n, 67}] (* Michael De Vlieger, Sep 08 2016 *) -
PARI
a(n) = {my(f = factor(n), p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res}; \\ David A. Corneth, Mar 08 2019 -
PARI
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)}; A156552(n) = if(1==n, 0, if(!(n%2), 1+(2*A156552(n/2)), 2*A156552(A064989(n)))); \\ (based on the given recurrence) - Antti Karttunen, Mar 08 2019
-
Perl
# Program corrected per instructions from Leonid Broukhis. - Antti Karttunen, Jun 26 2014 # However, it gives correct answers only up to n=136, before corruption by a wrap-around effect. # Note that the correct answer for n=137 is A156552(137) = 4294967296. $max = $ARGV[0]; $pow = 0; foreach $i (2..$max) { @a = split(/ /, `factor $i`); shift @a; $shift = 0; $cur = 0; while ($n = int shift @a) { $prime{$n} = 1 << $pow++ if !defined($prime{$n}); $cur |= $prime{$n} << $shift++; } print "$cur, "; } print "\n"; (Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library, two different implementations) (definec (A156552 n) (cond ((= n 1) 0) (else (+ (A000079 (+ -2 (A001222 n) (A061395 n))) (A156552 (A052126 n)))))) (definec (A156552 n) (cond ((= 1 n) (- n 1)) ((even? n) (+ 1 (* 2 (A156552 (/ n 2))))) (else (* 2 (A156552 (A064989 n)))))) ;; Antti Karttunen, Jun 26 2014
-
Python
from sympy import primepi, factorint def A156552(n): return sum((1<
Formula
From Antti Karttunen, Jun 26 2014: (Start)
a(1) = 0, a(2n) = 1+2*a(n), a(2n+1) = 2*a(A064989(2n+1)). [Compare to the entanglement recurrence A243071].
For n >= 0, a(2n+1) = 2*A244153(n+1). [Follows from the latter clause of the above formula.]
a(n) = A005941(n) - 1.
As a composition of related permutations:
For all n >= 1, A005940(1+a(n)) = n and for all n >= 0, a(A005940(n+1)) = n. [The offset-0 version of A005940 works as an inverse for this permutation.]
(End)
From Antti Karttunen, Oct 09 2016: (Start)
a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
For all n >= 0:
(End)
From Antti Karttunen, Dec 30 2017: (Start)
For n > 1, a(n) = Sum_{d|n, d>1} 2^A033265(a(d)). [See comments.]
More linking formulas:
(End)
From Antti Karttunen, Mar 08 2019: (Start)
The following sequences are derived from or related to the base-2 expansion of a(n):
The following sequences are obtained by applying to a(n) a function that depends on the prime factorization of its argument, which goes "against the grain" because a(n) is the binary code of the factorization of n, which in these cases is then factored again:
(End)
Extensions
More terms from Antti Karttunen, Jun 28 2014
Comments