A243354 -id:A243354

Search: a243354 -id:a243354

Displaying 1-9 of 9 results found.

page 1

A297156

Möbius transform of A243354.

+20
5

0, 1, 3, 1, 7, 2, 15, 3, 1, 6, 31, 6, 63, 14, 2, 5, 127, 2, 255, 14, 10, 30, 511, 10, 1, 62, 7, 30, 1023, 4, 2047, 11, 26, 126, 2, 2, 4095, 254, 58, 26, 8191, 12, 16383, 62, 14, 510, 32767, 22, 1, 2, 122, 126, 65535, 6, 18, 58, 250, 1022, 131071, 4, 262143, 2046, 30, 21, 50, 28, 524287, 254, 506, 4, 1048575, 6

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..4096

PROG

(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))));

A006068(n)= { my(s=1, ns); while(1, ns = n >> s; if(0==ns, break()); n = bitxor(n, ns); s <<= 1; ); return (n); } \\ Essentially Joerg Arndt's Jul 19 2012 code.

A243354(n) = A006068(A156552(n));

A297156(n) = sumdiv(n, d, moebius(n/d)*A243354(d));

CROSSREFS

Cf. A006068, A156552, A243354, A297157 (rgs-transform of this sequence).

Cf. also A297112, A297171, A297172.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Dec 28 2017

STATUS

approved

A297157

Restricted growth sequence transform of A297156, which is Möbius transform of A243354.

+20
5

1, 2, 3, 2, 4, 5, 6, 3, 2, 7, 8, 7, 9, 10, 5, 11, 12, 5, 13, 10, 14, 15, 16, 14, 2, 17, 4, 15, 18, 19, 20, 21, 22, 23, 5, 5, 24, 25, 26, 22, 27, 28, 29, 17, 10, 30, 31, 32, 2, 5, 33, 23, 34, 7, 35, 26, 36, 37, 38, 19, 39, 40, 15, 41, 42, 43, 44, 25, 45, 19, 46, 7, 47, 48, 7, 30, 5, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 33

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..8192

PROG

(PARI)

up_to = 8192;

rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om, invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om, invec[i], i); outvec[i] = u; u++ )); outvec; };

write_to_bfile(start_offset, vec, bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }

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

A006068(n)= { my(s=1, ns); while(1, ns = n >> s; if(0==ns, break()); n = bitxor(n, ns); s <<= 1; ); return (n); } \\ Essentially Joerg Arndt's Jul 19 2012 code.

A243354(n) = A006068(A156552(n));

A297156(n) = sumdiv(n, d, moebius(n/d)*A243354(d));

write_to_bfile(1, rgs_transform(vector(up_to, n, A297156(n))), "b297157.txt");

CROSSREFS

Cf. A006068, A156552, A243354, A297156.

Cf. also A297113, A297161, A297162.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Dec 28 2017

STATUS

approved

A056239

If n = Product_{k >= 1} (p_k)^(c_k) where p_k is k-th prime and c_k >= 0 then a(n) = Sum_{k >= 1} k*c_k.

+10
1657

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 6, 5, 5, 4, 7, 5, 8, 5, 6, 6, 9, 5, 6, 7, 6, 6, 10, 6, 11, 5, 7, 8, 7, 6, 12, 9, 8, 6, 13, 7, 14, 7, 7, 10, 15, 6, 8, 7, 9, 8, 16, 7, 8, 7, 10, 11, 17, 7, 18, 12, 8, 6, 9, 8, 19, 9, 11, 8, 20, 7, 21, 13, 8, 10, 9, 9, 22, 7, 8, 14, 23, 8, 10, 15, 12, 8, 24, 8, 10

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

A pseudo-logarithmic function in the sense that a(b*c) = a(b)+a(c) and so a(b^c) = c*a(b) and f(n) = k^a(n) is a multiplicative function. [Cf. A248692 for example.] Essentially a function from the positive integers onto the partitions of the nonnegative integers (1->0, 2->1, 3->2, 4->1+1, 5->3, 6->1+2, etc.) so each value a(n) appears A000041(a(n)) times, first with the a(n)-th prime and last with the a(n)-th power of 2. Produces triangular numbers from primorials. - Henry Bottomley, Nov 22 2001

Michael Nyvang writes (May 08 2006) that the Danish composer Karl Aage Rasmussen discovered this sequence in the 1990's: it has excellent musical properties.

All A000041(a(n)) different n's with the same value a(n) are listed in row a(n) of triangle A215366. - Alois P. Heinz, Aug 09 2012

a(n) is the sum of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(33) = 7 because the partition with Heinz number 33 = 3 * 11 is [2,5]. - Emeric Deutsch, May 19 2015

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Index entries for sequences computed from indices in prime factorization

FORMULA

Totally additive with a(p) = PrimePi(p), where PrimePi(n) = A000720(n).

a(n) = Sum_{k=1..A001221(n)} A049084(A027748(k))*A124010(k). - Reinhard Zumkeller, Apr 27 2013

From Antti Karttunen, Oct 11 2014: (Start)

a(n) = n - A178503(n).

a(n) = A161511(A156552(n)).

a(n) = A227183(A243354(n)).

For all n >= 0:

a(A002110(n)) = A000217(n). [Cf. Henry Bottomley's comment above.]

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

a(A243353(n)) = A227183(n).

Also, for all n >= 1:

a(A241909(n)) = A243503(n).

a(A122111(n)) = a(n).

a(A242424(n)) = a(n).

A248692(n) = 2^a(n). (End)

a(n) < A329605(n), a(n) = A001222(A108951(n)), a(A329902(n)) = A112778(n). - Antti Karttunen, Jan 14 2020

EXAMPLE

a(12) = 1*2 + 2*1 = 4, since 12 = 2^2 *3^1 = (p_1)^2 *(p_2)^1.

MAPLE

# To get 10000 terms. First make prime table: M:=10000; pl:=array(1..M); for i from 1 to M do pl[i]:=0; od: for i from 1 to M do if ithprime(i) > M then break; fi; pl[ithprime(i)]:=i; od:

# Decode Maple's amazing syntax for factoring integers: g:=proc(n) local e, p, t1, t2, t3, i, j, k; global pl; t1:=ifactor(n); t2:=nops(t1); if t2 = 2 and whattype(t1) <> `*` then p:=op(1, op(1, t1)); e:=op(2, t1); t3:=pl[p]*e; else

t3:=0; for i from 1 to t2 do j:=op(i, t1); if nops(j) = 1 then e:=1; p:=op(1, j); else e:=op(2, j); p:=op(1, op(1, j)); fi; t3:=t3+pl[p]*e; od: fi; t3; end; # N. J. A. Sloane, May 10 2006

A056239 := proc(n) add( numtheory[pi](op(1, p))*op(2, p), p = ifactors(n)[2]) ; end proc: # R. J. Mathar, Apr 20 2010

# alternative:

with(numtheory): a := proc (n) local B: B := proc (n) local nn, j, m: nn := op(2, ifactors(n)): for j to nops(nn) do m[j] := op(j, nn) end do: [seq(seq(pi(op(1, m[i])), q = 1 .. op(2, m[i])), i = 1 .. nops(nn))] end proc: add(B(n)[i], i = 1 .. nops(B(n))) end proc: seq(a(n), n = 1 .. 130); # Emeric Deutsch, May 19 2015

MATHEMATICA

a[1] = 0; a[2] = 1; a[p_?PrimeQ] := a[p] = PrimePi[p];

a[n_] := a[n] = Total[#[[2]]*a[#[[1]]] & /@ FactorInteger[n]]; a /@ Range[91] (* Jean-François Alcover, May 19 2011 *)

Table[Total[FactorInteger[n] /. {p_, c_} /; p > 0 :> PrimePi[p] c], {n, 91}] (* Michael De Vlieger, Jul 12 2017 *)

PROG

(Haskell)

a056239 n = sum $ zipWith (*) (map a049084 $ a027748_row n) (a124010_row n)

-- Reinhard Zumkeller, Apr 27 2013

(PARI) A056239(n) = if(1==n, 0, my(f=factor(n)); sum(i=1, #f~, f[i, 2] * primepi(f[i, 1]))); \\ Antti Karttunen, Oct 26 2014, edited Jan 13 2020

(Scheme)

(require 'factor) ;; Uses the function factor available in Aubrey Jaffer's SLIB Scheme library.

(define (A056239 n) (apply + (map A049084 (factor n))))

;; Antti Karttunen, Oct 26 2014

(Python)

from sympy import primepi, factorint

def A056239(n): return sum(primepi(p)*e for p, e in factorint(n).items()) # Chai Wah Wu, Jan 01 2023

CROSSREFS

Row sums of A112798.

Cf. A003963 (gives the corresponding products).

Cf. also A000041, A000217, A000720, A001221, A001222, A002110, A005940, A008475, A027748, A049084, A060437, A081401, A082090, A088314, A088318, A088850, A088880, A088881, A088887, A088902, A108951, A122111, A124010, A127668, A141128, A153734, A154351, A156552, A163517, A178503, A215366, A215369, A215501, A242422, A242423, A242424, A243070, A243353, A243354, A243503, A248692, A249336, A249337, A329605, A329902.

KEYWORD

easy,nonn,hear

AUTHOR

Leroy Quet, Aug 19 2000

STATUS

approved

A156552

Unary-encoded compressed factorization of natural numbers.

+10
372

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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

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

FORMULA

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)

EXAMPLE

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.

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

PROG

(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

(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

(Python)

from sympy import primepi, factorint

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

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.

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.

KEYWORD

easy,base,nonn

AUTHOR

Leonid Broukhis, Feb 09 2009

EXTENSIONS

More terms from Antti Karttunen, Jun 28 2014

STATUS

approved

A003963

Fully multiplicative with a(p) = k if p is the k-th prime.

+10
364

1, 1, 2, 1, 3, 2, 4, 1, 4, 3, 5, 2, 6, 4, 6, 1, 7, 4, 8, 3, 8, 5, 9, 2, 9, 6, 8, 4, 10, 6, 11, 1, 10, 7, 12, 4, 12, 8, 12, 3, 13, 8, 14, 5, 12, 9, 15, 2, 16, 9, 14, 6, 16, 8, 15, 4, 16, 10, 17, 6, 18, 11, 16, 1, 18, 10, 19, 7, 18, 12, 20, 4, 21, 12, 18, 8, 20, 12, 22, 3, 16, 13, 23, 8, 21, 14, 20, 5

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

a(n) is the Matula number of the rooted tree obtained from the rooted tree T having Matula number n, by contracting its edges that emanate from the root. Example: a(49) = 16. Indeed, the rooted tree with Matula number 49 is the tree obtained by merging two copies of the tree Y at their roots. Contracting the two edges that emanate from the root, we obtain the star tree with 4 edges having Matula number 16. - Emeric Deutsch, May 01 2015

The Matula (or Matula-Goebel) number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T. - Emeric Deutsch, May 01 2015

a(n) is the product of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(75) = 18; indeed, the partition having Heinz number 75 = 3*5*5 is [2,3,3] and 2*3*3 = 18. - Emeric Deutsch, Jun 03 2015

Let T be the free-commutative-monoid monad on the category Set. Then for each set N we have a canonical function m from TTN to TN. If we let N = {1, 2, 3, ...} and enumerate the primes in the usual way (A000040) then unique prime factorization gives a canonical bijection f from N to TN. Then the sequence is given by a(n) = f^-1(m(T(f)(f(n)))). - Oscar Cunningham, Jul 18 2019

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.

F. Göbel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.

I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.

I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.

D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Index entries for sequences related to Matula-Göbel numbers

Index entries for sequences computed from indices in prime factorization

FORMULA

If n = product prime(k)^e(k) then a(n) = product k^e(k).

Multiplicative with a(p^e) = A000720(p)^e. - David W. Wilson, Aug 01 2001

a(n) = Product_{k=1..A001221(n)} A049084(A027748(n,k))^A124010(n,k). - Reinhard Zumkeller, Jun 30 2012

Rec. eq.: a(1)=1, a(k-th prime) = a(k), a(rs)=a(r)a(s). The Maple program is based on this. - Emeric Deutsch, May 01 2015

a(n) = A243504(A241909(n)) = A243499(A156552(n)) = A227184(A243354(n)) - Antti Karttunen, Mar 07 2017

MAPLE

with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then pi(n) else a(r(n))*a(s(n)) end if end proc: seq(a(n), n = 1 .. 88);

# Alternative:

seq(mul(numtheory:-pi(t[1])^t[2], t=ifactors(n)[2]), n=1..100); # Robert Israel, May 01 2015

MATHEMATICA

a[n_] := Times @@ (PrimePi[ #[[1]] ]^#[[2]]& /@ FactorInteger[n]); a[1] = 1; Table[a[n], {n, 1, 88}]

PROG

(PARI) a(n)=f=factor(n); prod(i=1, #f[, 1], primepi(f[i, 1])^f[i, 2]) \\ Charles R Greathouse IV, Apr 26 2012; corrected by Rémy Sigrist, Jul 18 2019

(PARI) a(n) = {f = factor(n); for (i=1, #f~, f[i, 1] = primepi(f[i, 1]); ); factorback(f); } \\ Michel Marcus, Feb 08 2015

(PARI) A003963(n)={n=factor(n); n[, 1]=apply(primepi, n[, 1]); factorback(n)} \\ M. F. Hasler, May 03 2018

(Haskell)

a003963 n = product $

zipWith (^) (map a049084 $ a027748_row n) (a124010_row n)

-- Reinhard Zumkeller, Jun 30 2012

(Python)

from math import prod

from sympy import primepi, factorint

def A003963(n): return prod(primepi(p)**e for p, e in factorint(n).items()) # Chai Wah Wu, Nov 17 2022

CROSSREFS

Cf. A000720, A001221, A001222, A027748, A049084, A056239, A064553, A124010, A156552, A215366, A227184, A241909, A243354, A243499, A243504.

Product of entries on row n of A112798.

KEYWORD

nonn,nice,easy,mult

AUTHOR

Marc LeBrun

STATUS

approved

A242424

Bulgarian solitaire operation on partition list A112798: a(1) = 1, a(n) = A000040(A001222(n)) * A064989(n).

+10
17

1, 2, 4, 3, 6, 6, 10, 5, 12, 9, 14, 10, 22, 15, 18, 7, 26, 20, 34, 15, 30, 21, 38, 14, 27, 33, 40, 25, 46, 30, 58, 11, 42, 39, 45, 28, 62, 51, 66, 21, 74, 50, 82, 35, 60, 57, 86, 22, 75, 45, 78, 55, 94, 56, 63, 35, 102, 69, 106, 42, 118, 87, 100, 13, 99, 70, 122, 65

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

In "Bulgarian solitaire" a deck of cards or another finite set of objects is divided into one or more piles, and the "Bulgarian operation" is performed by taking one card from each pile, and making a new pile of them, which is added to the remaining set of piles. Essentially, this operation is a function whose domain and range are unordered integer partitions (cf. A000041) and which preserves the total size of a partition (the sum of its parts). This sequence is induced when the operation is implemented on the partitions as ordered by the list A112798.

Please compare to the definition of A122111, which conjugates the partitions encoded with the same system.

a(n) is even if and only if n is either a prime or a multiple of three.

Conversely, a(n) is odd if and only if n is a nonprime not divisible by three.

REFERENCES

Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..8192

Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).

Wikipedia, Bulgarian solitaire

Index entries for sequences computed from indices in prime factorization

FORMULA

a(1) = 1, a(n) = A000040(A001222(n)) * A064989(n) = A105560(n) * A064989(n).

a(n) = A241909(A243051(A241909(n))).

a(n) = A243353(A226062(A243354(n))).

a(A000079(n)) = A000040(n) for all n.

A056239(a(n)) = A056239(n) for all n.

PROG

(Scheme) (define (A242424 n) (if (<= n 1) n (* (A000040 (A001222 n)) (A064989 n))))

CROSSREFS

Row 1 of A243070 (table which gives successive "recursive iterates" of this sequence and converges towards A122111).

Fixed points: A002110 (primorial numbers).

Cf. A000041, A243051, A243072, A243073, A226062, A242422, A242423, A122111, A105560, A000040, A001222, A064989, A056239.

KEYWORD

nonn

AUTHOR

Antti Karttunen, May 13 2014

STATUS

approved

A226062

a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.

+10
16

0, 1, 3, 2, 13, 7, 6, 6, 11, 29, 15, 58, 9, 14, 4, 14, 19, 27, 61, 54, 245, 31, 122, 52, 27, 25, 30, 50, 25, 12, 12, 30, 35, 23, 59, 46, 237, 125, 118, 44, 235, 501, 63, 1002, 233, 250, 116, 40, 51, 19, 57, 38, 229, 62, 114, 36, 59, 17, 28, 34, 57, 8, 28, 62

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

For this sequence the partitions are encoded in the binary expansion of n in the same way as in A129594.

In "Bulgarian solitaire" a deck of cards or another finite set of objects is divided into one or more piles, and the "Bulgarian operation" is performed by taking one card from each pile, and making a new pile of them. The question originally posed was: on what condition the resulting partitions will eventually reach a fixed point, that is, a collection of piles that will be unchanged by the operation. See Martin Gardner reference and the Wikipedia-page.

A037481 gives the fixed points of this sequence, which are numbers that encode triangular partitions: 1 + 2 + 3 + ... + n.

A227752(n) tells how many times n occurs in this sequence, and A227753 gives the terms that do not occur here.

Of further interest: among each A000041(n) numbers j_i: j1, j2, ..., jk for which A227183(j_i)=n, how many cycles occur and what is the size of the largest one? (Both are 1 when n is in A000217, as then the fixed points are the only cycles.) Cf. A185700, A188160.

Also, A123975 answers how many Garden of Eden partitions there are for the deck of size n in Bulgarian Solitaire, corresponding to values that do not occur as the terms of this sequence.

REFERENCES

Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..8191

Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).

Antti Karttunen, Python-program for computing this and related sequences.

Wikipedia, Bulgarian solitaire

FORMULA

Other identities:

A227183(a(n)) = A227183(n). [This operation doesn't change the total sum of the partition.]

a(n) = A243354(A242424(A243353(n))).

a(n) = A075158(A243051(1+A075157(n))-1).

EXAMPLE

5 has binary expansion "101", whose runlengths are [1,1,1], which are converted to nonordered partition {1+1+1}.

6 has binary expansion "110", whose runlengths are [1,2] (we scan the runs of bits from right to left), which are converted to nonordered partition {1+2}.

7 has binary expansion "111", whose list of runlengths is [3], which is converted to partition {3}.

In "Bulgarian Operation" we subtract one from each part (with 1-parts vanishing), and then add a new part of the same size as there originally were parts, so that the total sum stays same.

Thus starting from a partition encoded by 5, {1,1,1} the operation works as 1-1, 1-1, 1-1 (all three 1's vanish) but appends part 3 as there originally were three parts, thus we get a new partition {3}. Thus a(5)=7.

From the partition {3} -> 3-1 and 1, which gives a new partition {1,2}, so a(7)=6.

For partition {1+2} -> 1-1 and 2-1, thus the first part vanishes, and the second is now 1, to which we add the new part 2, as there were two parts originally, thus {1+2} stays as {1+2}, and we have reached a fixed point, a(6)=6.

PROG

(MIT/GNU Scheme)

(define (A226062 n) (if (zero? n) n (ascpart_to_binexp (bulgarian-operation (binexp_to_ascpart n)))))

(define (bulgarian-operation ascpart) (let loop ((newpart (list (length ascpart))) (ascpart ascpart)) (cond ((null? ascpart) (sort newpart <)) (else (loop (if (= 1 (car ascpart)) newpart (cons (- (car ascpart) 1) newpart)) (cdr ascpart))))))

;; The rest is the same code as used in A129594:

(define (binexp_to_ascpart n) (let ((runlist (reverse! (binexp->runcount1list n)))) (PARTSUMS (cons (car runlist) (map -1+ (cdr runlist))))))

(define (ascpart_to_binexp ascpart) (runcount1list->binexp (reverse! (cons (car ascpart) (map 1+ (DIFF ascpart))))))

(define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))

(define (runcount1list->binexp lista) (let loop ((lista lista) (s 0) (state 1)) (cond ((null? lista) s) (else (loop (cdr lista) (+ (* s (expt 2 (car lista))) (* state (- (expt 2 (car lista)) 1))) (- 1 state))))))

(define (DIFF a) (map - (cdr a) (reverse! (cdr (reverse a)))))

(define (PARTSUMS a) (cdr (reverse! (fold-left (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a))))

CROSSREFS

Cf. A227147, A227183, A227452.

Cf. A037481 (gives the fixed points).

Cf. A227752 (how many times n occurs here).

Cf. A227753 (numbers that do not occur here).

Cf. A129594 (conjugates the partitions encoded with the same system).

Cf. also A123975, A074909, A185700, A071762, A075157, A075158, A243353, A243354, A242424, A243051.

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, Jul 06 2013

STATUS

approved

A243353

Permutation of natural numbers which maps between the partitions as encoded in A227739 (binary based system, zero-based) to A112798 (prime-index based system, one-based).

+10
15

1, 2, 4, 3, 9, 8, 6, 5, 25, 18, 16, 27, 15, 12, 10, 7, 49, 50, 36, 75, 81, 32, 54, 125, 35, 30, 24, 45, 21, 20, 14, 11, 121, 98, 100, 147, 225, 72, 150, 245, 625, 162, 64, 243, 375, 108, 250, 343, 77, 70, 60, 105, 135, 48, 90, 175, 55, 42, 40, 63, 33, 28, 22, 13, 169, 242, 196, 363, 441, 200, 294, 605, 1225, 450, 144

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Note the indexing: the domain includes zero, but the range starts from one.

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..8192

Index entries for sequences that are permutations of the natural numbers

FORMULA

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

a(n) = A241909(1+A075157(n)). [With A075157's original starting offset]

For all n >= 0, A243354(a(n)) = n.

A227183(n) = A056239(a(n)). [Maps between the corresponding sums ...]

A227184(n) = A003963(a(n)). [... and products of parts of each partition].

For n >= 0, a(A037481(n)) = A002110(n). [Also "triangular partitions", the fixed points of Bulgarian solitaire, A226062 & A242424].

For n >= 1, a(A227451(n+1)) = 4*A243054(n).

MATHEMATICA

f[n_, i_, x_] := Which[n == 0, x, EvenQ@ n, f[n/2, i + 1, x], True, f[(n - 1)/2, i, x Prime@ i]]; Table[f[BitXor[n, Floor[n/2]], 1, 1], {n, 0, 74}] (* Michael De Vlieger, May 09 2017 *)

PROG

(Scheme) (define (A243353 n) (A005940 (+ 1 (A003188 n))))

(Python)

from sympy import prime

import math

def A(n): return n - 2**int(math.floor(math.log(n, 2)))

def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))

def a005940(n): return b(n - 1)

def a003188(n): return n^int(n/2)

def a243353(n): return a005940(1 + a003188(n)) # Indranil Ghosh, May 07 2017

CROSSREFS

A243354 gives the inverse mapping.

Cf. A227739, A112798, A075157, A241909, A005940, A003188, A226062, A242424.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 05 2014

STATUS

approved

A286556

Permutation of nonnegative integers: a(n) = A006068(A252754(n)).

+10
2

0, 1, 3, 2, 7, 6, 15, 5, 4, 14, 31, 13, 63, 30, 12, 10, 127, 9, 255, 29, 11, 62, 511, 26, 8, 126, 28, 61, 1023, 25, 2047, 21, 27, 254, 24, 18, 4095, 510, 60, 58, 8191, 22, 16383, 125, 20, 1022, 32767, 53, 16, 17, 19, 253, 65535, 57, 23, 122, 59, 2046, 131071, 50, 262143, 4094, 124, 42, 56, 54, 524287, 509, 52, 49, 1048575, 37

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Note the indexing: the domain starts from one, but the range includes also zero.

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..1024

Index entries for sequences that are permutations of the natural numbers

FORMULA

a(n) = A006068(A252754(n)).

PROG

(Scheme) (define (A286556 n) (A006068 (A252754 n)))