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