A153013 -id:A153013 - cp's OEIS frontend

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

Leonid Broukhis, Feb 09 2009

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.
From Antti Karttunen, Jun 27 2014: (Start)
The odd bisection (containing even terms) halved gives A244153.
The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.
(End)
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

			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.

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

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.
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.
Other related permutations: A253551, A253792, A253564, A253791, A277195, A297163, A297164, A297165, A297166, A302023, A305418, A322863, A322864.

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 *)

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

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

# 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

from sympy import primepi, factorint
def A156552(n): return sum((1<Chai Wah Wu, Mar 10 2023

From Antti Karttunen, Jun 26 2014: (Start)
a(1) = 0, a(n) = A000079(A001222(n)+A061395(n)-2) + a(A052126(n)).
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:
a(n) = A003188(A243354(n)).
a(n) = A054429(A243071(n)).
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.]
This permutations also maps between the partition-lists A112798 and A125106:
A056239(n) = A161511(a(n)). [The sums of parts of each partition (the total sizes).]
A003963(n) = A243499(a(n)). [And also the products of those parts.]
(End)
From Antti Karttunen, Oct 09 2016: (Start)
A161511(a(n)) = A056239(n).
A029837(1+a(n)) = A252464(n). [Binary width of terms.]
A080791(a(n)) = A252735(n). [Number of nonleading 0-bits.]
A000120(a(n)) = A001222(n). [Binary weight.]
For all n >= 2, A001511(a(n)) = A055396(n).
For all n >= 2, A000120(a(n))-1 = A252736(n). [Binary weight minus one.]
A252750(a(n)) = A252748(n).
a(A250246(n)) = A252754(n).
a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
A085357(a(n)) = A008966(n). [Ditto for their characteristic functions.]
For all n >= 0:
a(A276076(n)) = A277012(n).
a(A276086(n)) = A277022(n).
a(A260443(n)) = A277020(n).
(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:
A106737(a(n)) = A000005(n).
A290077(a(n)) = A000010(n).
A069010(a(n)) = A001221(n).
A136277(a(n)) = A181591(n).
A132971(a(n)) = A008683(n).
A106400(a(n)) = A008836(n).
A268411(a(n)) = A092248(n).
A037011(a(n)) = A010052(n) [conjectured, depends on the exact definition of A037011].
A278161(a(n)) = A046951(n).
A001316(a(n)) = A061142(n).
A277561(a(n)) = A034444(n).
A286575(a(n)) = A037445(n).
A246029(a(n)) = A181819(n).
A278159(a(n)) = A124859(n).
A246660(a(n)) = A112624(n).
A246596(a(n)) = A069739(n).
A295896(a(n)) = A053866(n).
A295875(a(n)) = A295297(n).
A284569(a(n)) = A072411(n).
A286574(a(n)) = A064547(n).
A048735(a(n)) = A292380(n).
A292272(a(n)) = A292382(n).
A244154(a(n)) = A048673(n), a(A064216(n)) = A244153(n).
A279344(a(n)) = A279339(n), a(A279338(n)) = A279343(n).
a(A277324(n)) = A277189(n).
A037800(a(n)) = A297155(n).
For n > 1, A033265(a(n)) = 1+A297113(n).
(End)
From Antti Karttunen, Mar 08 2019: (Start)
a(n) = A048675(n) + A323905(n).
a(A324201(n)) = A000396(n), provided there are no odd perfect numbers.
The following sequences are derived from or related to the base-2 expansion of a(n):
A000265(a(n)) = A322993(n).
A002487(a(n)) = A323902(n).
A005187(a(n)) = A323247(n).
A324288(a(n)) = A324116(n).
A323505(a(n)) = A323508(n).
A079559(a(n)) = A323512(n).
A085405(a(n)) = A323239(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:
A000203(a(n)) = A323243(n).
A033879(a(n)) = A323244(n) = 2*a(n) - A323243(n),
A294898(a(n)) = A323248(n).
A000005(a(n)) = A324105(n).
A000010(a(n)) = A324104(n).
A083254(a(n)) = A324103(n).
A001227(a(n)) = A324117(n).
A000593(a(n)) = A324118(n).
A001221(a(n)) = A324119(n).
A009194(a(n)) = A324396(n).
A318458(a(n)) = A324398(n).
A192895(a(n)) = A324100(n).
A106315(a(n)) = A324051(n).
A010052(a(n)) = A324822(n).
A053866(a(n)) = A324823(n).
A001065(a(n)) = A324865(n) = A323243(n) - a(n),
A318456(a(n)) = A324866(n) = A324865(n) OR a(n),
A318457(a(n)) = A324867(n) = A324865(n) XOR a(n),
A318458(a(n)) = A324398(n) = A324865(n) AND a(n),
A318466(a(n)) = A324819(n) = A323243(n) OR 2*a(n),
A318467(a(n)) = A324713(n) = A323243(n) XOR 2*a(n),
A318468(a(n)) = A324815(n) = A323243(n) AND 2*a(n).
(End)

More terms from Antti Karttunen, Jun 28 2014

A106737 a(n) = Sum_{k=0..n} ({binomial(n+k,n-k)*binomial(n,k)} mod 2).

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 3, 4, 2, 4, 4, 6, 3, 6, 4, 5, 2, 4, 4, 6, 4, 8, 6, 8, 3, 6, 6, 9, 4, 8, 5, 6, 2, 4, 4, 6, 4, 8, 6, 8, 4, 8, 8, 12, 6, 12, 8, 10, 3, 6, 6, 9, 6, 12, 9, 12, 4, 8, 8, 12, 5, 10, 6, 7, 2, 4, 4, 6, 4, 8, 6, 8, 4, 8, 8, 12, 6, 12, 8, 10, 4, 8, 8, 12, 8, 16, 12, 16, 6, 12, 12, 18, 8, 16, 10, 12

Offset: 0

Benoit Cloitre, May 15 2005

nonn

The formula (the recurrence, if confirmed to be equal to sum binomial formula) implies that this is the run length transform of the sequence 1,2,3,4,5,... - N. J. A. Sloane, Feb 05 2015. Note: That sequence should be considered as a successor function a(n) = n+1, starting from offset 0. See also A020725. - Antti Karttunen, Oct 15 2016

The recurrence formula is correct. See paper in links. - Chai Wah Wu, Oct 16 2016

Chai Wah Wu, Table of n, a(n) for n = 0..10000
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166 [math.CO], 2016.

Row sums of triangle in A253084.
Cf. A000005, A005940, A020725, A227349, A277335 (positions of odd terms).
Cf. also A153013.

Table[Sum[Mod[#, 2] &[Binomial[n + k, n - k] Binomial[n, k]], {k, 0, n}], {n, 0, 95}] (* Michael De Vlieger, Oct 17 2016 *)

a(n) = sum(k=0, n, (binomial(n+k,n-k)*binomial(n,k)) % 2); \\ Michel Marcus, Dec 08 2013

def A106737(n):
    return sum(int(not (~(n+k) & (n-k)) | (~n & k)) for k in range(n+1)) # Chai Wah Wu, Feb 09 2016
(Scheme, two mathematically equal implementations, based on RLT-interpretation)
;; The first one implements the given recurrence and uses memoization-macro definec:
(definec (A106737 n) (cond ((zero? n) 1) ((even? n) (A106737 (/ n 2))) ((= 1 (modulo n 4)) (* 2 (A106737 (/ (- n 1) 2)))) (else (- (* 2 (A106737 (/ (- n 1) 2))) (A106737 (/ (- n 3) 4))))))
;; This one applies the Run Length Transform explicitly to r -> r+1 function:
(define (A106737 n) (fold-left (lambda (a r) (* a (+ 1 r))) 1 (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2))))) ;; See A227349 for the required other functions.
;; Antti Karttunen, Oct 15 2016

a(0)=1, a(2n) = a(n), a(4n+1) = 2*a(2n), a(4n+3) = 2*a(2n+1) - a(n).
From Antti Karttunen, Oct 15 2016: (Start)
a(n) = A000005(A005940(1+n)). [Follows from the Run Length Transform-interpretation.]
For n > 1, a(n^2) is always even. [Based on RLT-interpretation. n^2 = 1 modulo 4 for all odd n and ((2^k)*n)^2 = 2^(2k) * (n^2), thus the last 1-bit is always alone and contributes 2 to the product, making it even.]
(End)

The unique infinite sequence such that a(0) = 0, a(n) = A276085(a(n+1)) for n >= 0, and A129251(a(n)) = 0 for n >= 1, i.e., all nonzero terms must be in A048103.

a(10) is 240 decimal digits long (can be found in b-file), and a(11) is too big to fit even into a b-file as it is 32700 decimal digits long, but it can be found in the given a-file.

After the initial 1, even-indexed terms are of the form 4k+2 (members of A016825) and odd-indexed terms are of the form 6k+3 (members of A016945). However, not all even terms after 2 are multiples of three, because not all odd-indexed terms are of the form 4k+3. For example, because a(11) is of the form 4k+1, a(12) cannot be a multiple of three. - Antti Karttunen, Jun 18 2017

cp's OEIS Frontend

A156552 Unary-encoded compressed factorization of natural numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Perl

Python

Formula

Extensions

A106737 a(n) = Sum_{k=0..n} ({binomial(n+k,n-k)*binomial(n,k)} mod 2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A328316 Iterates of A276086 starting from 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A109162 a(1) = 1; for n > 1, a(n) = A019565(a(n-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions