cp's OEIS Frontend

A156552 Unary-encoded compressed factorization of natural numbers.

%I A156552 #118 Mar 11 2023 08:07:12
%S A156552 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,
%T A156552 65,14,35,512,21,1024,31,34,129,20,27,2048,257,66,39,4096,37,8192,67,
%U A156552 22,513,16384,47,24,25,130,131,32768,29,36,71,258,1025,65536,43,131072,2049,38,63,68,69,262144
%N A156552 Unary-encoded compressed factorization of natural numbers.
%C A156552 The primes become the powers of 2 (2 -> 1, 3 -> 2, 5 -> 4, 7 -> 8); the composite numbers are formed by taking the values for the factors in the increasing order, multiplying them by the consecutive powers of 2, and summing. See the Example section.
%C A156552 From _Antti Karttunen_, Jun 27 2014: (Start)
%C A156552 The odd bisection (containing even terms) halved gives A244153.
%C A156552 The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.
%C A156552 (End)
%C A156552 Question: Are there any other solutions that would satisfy the recurrence r(1) = 0; and for n > 1, r(n) = Sum_{d|n, d>1} 2^A033265(r(d)), apart from simple variants 2^k * A156552(n)? See also A297112, A297113. - _Antti Karttunen_, Dec 30 2017
%H A156552 David A. Corneth, <a href="/A156552/b156552.txt">Table of n, a(n) for n = 1..10000</a> (first 1024 terms from Antti Karttunen)
%H A156552 Hans Havermann, <a href="/A156552/a156552.txt">Factorization of the first 10000 terms, in format [[primes], [exponents]]</a>
%H A156552 <a href="http://knop.livejournal.com/107484.html">A puzzle by Sergey Orlov (in Russian)</a>
%H A156552 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A156552 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%H A156552 <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%F A156552 From _Antti Karttunen_, Jun 26 2014: (Start)
%F A156552 a(1) = 0, a(n) = A000079(A001222(n)+A061395(n)-2) + a(A052126(n)).
%F A156552 a(1) = 0, a(2n) = 1+2*a(n), a(2n+1) = 2*a(A064989(2n+1)). [Compare to the entanglement recurrence A243071].
%F A156552 For n >= 0, a(2n+1) = 2*A244153(n+1). [Follows from the latter clause of the above formula.]
%F A156552 a(n) = A005941(n) - 1.
%F A156552 As a composition of related permutations:
%F A156552 a(n) = A003188(A243354(n)).
%F A156552 a(n) = A054429(A243071(n)).
%F A156552 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.]
%F A156552 This permutations also maps between the partition-lists A112798 and A125106:
%F A156552 A056239(n) = A161511(a(n)). [The sums of parts of each partition (the total sizes).]
%F A156552 A003963(n) = A243499(a(n)). [And also the products of those parts.]
%F A156552 (End)
%F A156552 From _Antti Karttunen_, Oct 09 2016: (Start)
%F A156552 A161511(a(n)) = A056239(n).
%F A156552 A029837(1+a(n)) = A252464(n). [Binary width of terms.]
%F A156552 A080791(a(n)) = A252735(n). [Number of nonleading 0-bits.]
%F A156552 A000120(a(n)) = A001222(n). [Binary weight.]
%F A156552 For all n >= 2, A001511(a(n)) = A055396(n).
%F A156552 For all n >= 2, A000120(a(n))-1 = A252736(n). [Binary weight minus one.]
%F A156552 A252750(a(n)) = A252748(n).
%F A156552 a(A250246(n)) = A252754(n).
%F A156552 a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
%F A156552 A085357(a(n)) = A008966(n). [Ditto for their characteristic functions.]
%F A156552 For all n >= 0:
%F A156552 a(A276076(n)) = A277012(n).
%F A156552 a(A276086(n)) = A277022(n).
%F A156552 a(A260443(n)) = A277020(n).
%F A156552 (End)
%F A156552 From _Antti Karttunen_, Dec 30 2017: (Start)
%F A156552 For n > 1, a(n) = Sum_{d|n, d>1} 2^A033265(a(d)). [See comments.]
%F A156552 More linking formulas:
%F A156552 A106737(a(n)) = A000005(n).
%F A156552 A290077(a(n)) = A000010(n).
%F A156552 A069010(a(n)) = A001221(n).
%F A156552 A136277(a(n)) = A181591(n).
%F A156552 A132971(a(n)) = A008683(n).
%F A156552 A106400(a(n)) = A008836(n).
%F A156552 A268411(a(n)) = A092248(n).
%F A156552 A037011(a(n)) = A010052(n) [conjectured, depends on the exact definition of A037011].
%F A156552 A278161(a(n)) = A046951(n).
%F A156552 A001316(a(n)) = A061142(n).
%F A156552 A277561(a(n)) = A034444(n).
%F A156552 A286575(a(n)) = A037445(n).
%F A156552 A246029(a(n)) = A181819(n).
%F A156552 A278159(a(n)) = A124859(n).
%F A156552 A246660(a(n)) = A112624(n).
%F A156552 A246596(a(n)) = A069739(n).
%F A156552 A295896(a(n)) = A053866(n).
%F A156552 A295875(a(n)) = A295297(n).
%F A156552 A284569(a(n)) = A072411(n).
%F A156552 A286574(a(n)) = A064547(n).
%F A156552 A048735(a(n)) = A292380(n).
%F A156552 A292272(a(n)) = A292382(n).
%F A156552 A244154(a(n)) = A048673(n), a(A064216(n)) = A244153(n).
%F A156552 A279344(a(n)) = A279339(n), a(A279338(n)) = A279343(n).
%F A156552 a(A277324(n)) = A277189(n).
%F A156552 A037800(a(n)) = A297155(n).
%F A156552 For n > 1, A033265(a(n)) = 1+A297113(n).
%F A156552 (End)
%F A156552 From _Antti Karttunen_, Mar 08 2019: (Start)
%F A156552 a(n) = A048675(n) + A323905(n).
%F A156552 a(A324201(n)) = A000396(n), provided there are no odd perfect numbers.
%F A156552 The following sequences are derived from or related to the base-2 expansion of a(n):
%F A156552 A000265(a(n)) = A322993(n).
%F A156552 A002487(a(n)) = A323902(n).
%F A156552 A005187(a(n)) = A323247(n).
%F A156552 A324288(a(n)) = A324116(n).
%F A156552 A323505(a(n)) = A323508(n).
%F A156552 A079559(a(n)) = A323512(n).
%F A156552 A085405(a(n)) = A323239(n).
%F A156552 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:
%F A156552 A000203(a(n)) = A323243(n).
%F A156552 A033879(a(n)) = A323244(n) = 2*a(n) - A323243(n),
%F A156552 A294898(a(n)) = A323248(n).
%F A156552 A000005(a(n)) = A324105(n).
%F A156552 A000010(a(n)) = A324104(n).
%F A156552 A083254(a(n)) = A324103(n).
%F A156552 A001227(a(n)) = A324117(n).
%F A156552 A000593(a(n)) = A324118(n).
%F A156552 A001221(a(n)) = A324119(n).
%F A156552 A009194(a(n)) = A324396(n).
%F A156552 A318458(a(n)) = A324398(n).
%F A156552 A192895(a(n)) = A324100(n).
%F A156552 A106315(a(n)) = A324051(n).
%F A156552 A010052(a(n)) = A324822(n).
%F A156552 A053866(a(n)) = A324823(n).
%F A156552 A001065(a(n)) = A324865(n) = A323243(n) - a(n),
%F A156552 A318456(a(n)) = A324866(n) = A324865(n) OR a(n),
%F A156552 A318457(a(n)) = A324867(n) = A324865(n) XOR a(n),
%F A156552 A318458(a(n)) = A324398(n) = A324865(n) AND a(n),
%F A156552 A318466(a(n)) = A324819(n) = A323243(n) OR 2*a(n),
%F A156552 A318467(a(n)) = A324713(n) = A323243(n) XOR 2*a(n),
%F A156552 A318468(a(n)) = A324815(n) = A323243(n) AND 2*a(n).
%F A156552 (End)
%e A156552 For 84 = 2*2*3*7 -> 1*1 + 1*2 + 2*4 + 8*8 =  75.
%e A156552 For 105 = 3*5*7 -> 2*1 + 4*2 + 8*4 = 42.
%e A156552 For 137 = p_33 -> 2^32 = 4294967296.
%e A156552 For 420 = 2*2*3*5*7 -> 1*1 + 1*2 + 2*4 + 4*8 + 8*16 = 171.
%e A156552 For 147 = 3*7*7 = p_2 * p_4 * p_4 -> 2*1 + 8*2 + 8*4 = 50.
%t A156552 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 *)
%o A156552 (Perl)
%o A156552 # Program corrected per instructions from _Leonid Broukhis_. - _Antti Karttunen_, Jun 26 2014
%o A156552 # However, it gives correct answers only up to n=136, before corruption by a wrap-around effect.
%o A156552 # Note that the correct answer for n=137 is A156552(137) = 4294967296.
%o A156552 $max = $ARGV[0];
%o A156552 $pow = 0;
%o A156552 foreach $i (2..$max) {
%o A156552 @a = split(/ /, `factor $i`);
%o A156552 shift @a;
%o A156552 $shift = 0;
%o A156552 $cur = 0;
%o A156552 while ($n = int shift @a) {
%o A156552 $prime{$n} = 1 << $pow++ if !defined($prime{$n});
%o A156552 $cur |= $prime{$n} << $shift++;
%o A156552 }
%o A156552 print "$cur, ";
%o A156552 }
%o A156552 print "\n";
%o A156552 (Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library, two different implementations)
%o A156552 (definec (A156552 n) (cond ((= n 1) 0) (else (+ (A000079 (+ -2 (A001222 n) (A061395 n))) (A156552 (A052126 n))))))
%o A156552 (definec (A156552 n) (cond ((= 1 n) (- n 1)) ((even? n) (+ 1 (* 2 (A156552 (/ n 2))))) (else (* 2 (A156552 (A064989 n))))))
%o A156552 ;; _Antti Karttunen_, Jun 26 2014
%o A156552 (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
%o A156552 (PARI)
%o A156552 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)};
%o A156552 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
%o A156552 (Python)
%o A156552 from sympy import primepi, factorint
%o A156552 def A156552(n): return sum((1<<primepi(p)-1)<<i for i, p in enumerate(factorint(n,multiple=True))) # _Chai Wah Wu_, Mar 10 2023
%Y A156552 One less than A005941.
%Y A156552 Inverse permutation: A005940 with starting offset 0 instead of 1.
%Y A156552 Cf. A000079, A000120, A001222, A052126, A054429, A061395, A064216, A064989, A003188, A243071, A243065-A243066, A244153, A243354, A112798, A125106, A056239, A161511.
%Y A156552 Cf. also A297106, A297112 (Möbius transform), A297113, A153013, A290308, A300827, A323243, A323244, A323247, A324201, A324812 (n for which a(n) is a square), A324813, A324822, A324823, A324398, A324713, A324815, A324819, A324865, A324866, A324867.
%Y A156552 Other related permutations: A253551, A253792, A253564, A253791, A277195, A297163, A297164, A297165, A297166, A302023, A305418, A322863, A322864.
%K A156552 easy,base,nonn
%O A156552 1,3
%A A156552 _Leonid Broukhis_, Feb 09 2009
%E A156552 More terms from _Antti Karttunen_, Jun 28 2014