A277022 -id:A277022 - 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

A276150 Sum of digits when n is written in primorial base (A049345); minimal number of primorials (A002110) that add to n.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 7, 8, 8, 9, 9, 10, 4

Offset: 0

Antti Karttunen, Aug 22 2016

The sum of digits of n in primorial base is odd if n is 1 or 2 (mod 4) and even if n is 0 or 3 (mod 4). Proof: primorials are 1 or 2 (mod 4) and a(n) can be constructed via the greedy algorithm. So if n = 4k + r where 0 <= r < 4, 4k needs an even number of primorials and r needs hammingweight(r) = A000120(r) primorials. Q.E.D. - David A. Corneth, Feb 27 2019

			For n=24, which is "400" in primorial base (as 24 = 4*(3*2*1) + 0*(2*1) + 0*1, see A049345), the sum of digits is 4, thus a(24) = 4.

Antti Karttunen, Table of n, a(n) for n = 0..30030
Index entries for sequences related to primorial base

Cf. A000120, A001222, A002110, A049345, A053589, A235168, A260188, A267263, A276084, A276086, A276151, A277022, A278226, A283477, A319713, A319715 (inverse Möbius transform), A321683, A324342, A324382, A324383, A324386, A324387, A371091, A373605, A373606, A373607.
Cf. A333426 [k such that a(k)|k], A339215 [numbers not of the form x+a(x) for any x], A358977 [k such that gcd(k, a(k)) = 1].
Cf. A338835, A366693.
Cf. A014601, A042963 (positions of even and odd terms), A343048 (positions of records).
Differs from analogous A034968 for the first time at n=24.

nn = 120; b = MixedRadix[Reverse@ Prime@ NestWhileList[# + 1 &, 1, Times @@ Prime@ Range[# + 1] <= nn &]]; Table[Total@ IntegerDigits[n, b], {n, 0, nn}] (* Version 10.2, or *)
nn = 120; f[n_] := Block[{a = {{0, n}}}, Do[AppendTo[a, {First@ #, Last@ #} &@ QuotientRemainder[a[[-1, -1]], Times @@ Prime@ Range[# - i]]], {i, 0, #}] &@ NestWhile[# + 1 &, 0, Times @@ Prime@ Range[# + 1] <= n &]; Rest[a][[All, 1]]]; Table[Total@ f@ n, {n, 0, 120}] (* Michael De Vlieger, Aug 26 2016 *)

A276150(n) = { my(s=0, p=2, d); while(n, d = (n%p); s += d; n = (n-d)/p; p = nextprime(1+p)); (s); }; \\ Antti Karttunen, Feb 27 2019

from sympy import prime, primefactors
def Omega(n): return 0 if n==1 else Omega(n//primefactors(n)[0]) + 1
def a276086(n):
    i=0
    m=pr=1
    while n>0:
        i+=1
        N=prime(i)*pr
        if n%N!=0:
            m*=(prime(i)**((n%N)/pr))
            n-=n%N
        pr=N
    return m
def a(n): return Omega(a276086(n))
print([a(n) for n in range(201)]) # Indranil Ghosh, Jun 23 2017

a(n) = 1 + a(A276151(n)) = 1 + a(n-A002110(A276084(n))), a(0) = 0.
or for n >= 1: a(n) = 1 + a(n-A260188(n)).
Other identities and observations. For all n >= 0:
a(n) = A001222(A276086(n)) = A001222(A278226(n)).
a(n) >= A371091(n) >= A267263(n).
From Antti Karttunen, Feb 27 2019: (Start)
a(n) = A000120(A277022(n)).
a(A283477(n)) = A324342(n).
(End)
a(n) = A373606(n) + A373607(n). - Antti Karttunen, Jun 19 2024

A277012 Factorial base representation of n is rewritten as a base-2 number with each nonzero digit k replaced by a run of k 1's (followed by one extra zero if not the rightmost run of 1's) and with each 0 kept as 0.

Original entry on oeis.org

0, 1, 2, 5, 6, 13, 4, 9, 10, 21, 22, 45, 12, 25, 26, 53, 54, 109, 28, 57, 58, 117, 118, 237, 8, 17, 18, 37, 38, 77, 20, 41, 42, 85, 86, 173, 44, 89, 90, 181, 182, 365, 92, 185, 186, 373, 374, 749, 24, 49, 50, 101, 102, 205, 52, 105, 106, 213, 214, 429, 108, 217, 218, 437, 438, 877, 220, 441, 442, 885, 886, 1773, 56, 113, 114, 229, 230, 461, 116, 233

Offset: 0

Antti Karttunen, Sep 25 2016

			9 = "111" in factorial base (3! + 2! + 1! = 9) is converted to three 1-bits with separating zeros between, in binary as "10101" = A007088(21), thus a(9) = 21.
91 = "3301" in factorial base (91 = 3*4! + 3*3! + 1!) is converted to binary number "1110111001" = A007088(953), thus a(91) = 953. Between the rightmost 1-runs the other zero comes from the factorial base representation, while the other zero is an extra separating zero inserted after each run of 1-bits apart from the rightmost 1-run. The single zero between the two leftmost 1-runs is similarly used to separate the two "unary representations" of 3's.

Cf. A000035, A000079, A000120, A000225, A007088, A007623, A034968, A060130, A069010, A156552, A227153, A227349.
Cf. A277008 (terms sorted into ascending order).
Cf. A277011 (a left inverse).
Differs from analogous A277022 for the first time at n=24, where a(24) = 8, while A277022(24) = 60.

(define (A277012 n) (let loop ((n n) (z 0) (i 2) (j 0)) (if (zero? n) z (let ((d (remainder n i))) (loop (quotient n i) (+ z (* (A000225 d) (A000079 j))) (+ 1 i) (+ 1 j d))))))

a(n) = A156552(A276076(n)).
Other identities. For all n >= 0:
A277011(a(n)) = n.
A005940(1+a(n)) = A276076(n).
A000035(a(n)) = A000035(n). [Preserves the parity of n.]
A000120(a(n)) = A034968(n).
A069010(a(n)) = A060130(n).
A227349(a(n)) = A227153(n).

A277017 Number of maximal runs of 1-bits (in binary expansion of n) such that the length of run >= A000040(1 + the total number of zeros to the right of that run).

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 2, 0

Offset: 0

Antti Karttunen, Sep 26 2016

a(n) = number of 1-runs in binary expansion of n that exceed the length allotted to that run by primorial base coding used in A277022. If a(n) = 0, then n is in the range of A277022.

			For n=3, "11" in binary, the only maximal run of 1-bits is of length 2, and 2 >= prime(0+1) (where 0 is the total number of zeros to the right of it), thus a(3) = 1.
For n=59, "111011" in binary, both the length of run "11" at the least significant end exceeds the limit (see case n=3 above), and also the length of run "111" >= prime(1 + the total number of 0's to the right of it) = prime(2) = 3, thus a(59) = 1+1 = 2.
For n=60, "111100" in binary, the length of only run of 1's is 4, and 4 < prime(2+1) = 5, thus a(60) = 0.

Cf. A277018 (positions of zeros), A277019 (of nonzeros).
Cf. A000040, A005940, A129251, A277021, A277022.
Differs from similar A277007 for the first time at n=60, where a(60)=0, while A277007(60)=1.

(define (A277017 n) (let loop ((e 0) (n n) (z 0) (r 0)) (cond ((zero? n) (+ e (if (>= r (A000040 (+ 1 z))) 1 0))) ((even? n) (loop (+ e (if (>= r (A000040 (+ 1 z))) 1 0)) (/ n 2) (+ 1 z) 0)) (else (loop e (/ (- n 1) 2) z (+ 1 r))))))

a(n) = A129251(A005940(1+n)).

cp's OEIS Frontend

A277018 Numbers n for which A277017(n) = 0; range of A277022 sorted into ascending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A277019 Numbers not in range of A277022.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A277021 Left inverse of A277022.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Scheme

Formula

A156552 Unary-encoded compressed factorization of natural numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Perl

Python

Formula

Extensions

A276150 Sum of digits when n is written in primorial base (A049345); minimal number of primorials (A002110) that add to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A277012 Factorial base representation of n is rewritten as a base-2 number with each nonzero digit k replaced by a run of k 1's (followed by one extra zero if not the rightmost run of 1's) and with each 0 kept as 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Scheme

Formula

A277017 Number of maximal runs of 1-bits (in binary expansion of n) such that the length of run >= A000040(1 + the total number of zeros to the right of that run).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula