A283528 -id:A283528 - cp's OEIS frontend

A283530 The number of reduced phi-partitions of n.

0, 0, 1, 1, 1, 0, 1, 2, 1, 1, 1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 3, 3, 1, 1, 2, 3, 3, 3, 1, 0, 1, 5, 4, 4, 3, 2, 1, 5, 4, 4, 1, 1, 1, 6, 6, 7, 1, 3, 2, 6, 5, 8, 1, 3, 4, 8, 6, 10, 1, 1, 1, 11, 9, 12, 5, 2, 1, 12, 8, 5, 1, 5, 1, 14, 13, 14, 5, 3, 1, 13, 9, 16, 1, 1

Offset: 1

R. J. Mathar, Mar 10 2017

nonn

The reduced phi-partitions of n are partitions n= a_1 +a_2 +a_3 +... +a_k into at least 2 parts such that each part is simple (i.e. each part in A002110, as required in A283529) and such that in addition phi(n) = sum_i phi(a_i), as required in A283528. phi(.) = A000010(.) is Euler's totient.

Numbers n where a(n)=1 are called semisimple. 3, 4, 5, 7, 9, 10, 11, 12, 13, 17, 18, 19, 23, 24,... are semisimple (see A283320). In this list of semisimple numbers there are no odd numbers besides 9 and the odd primes.

			a(15)=2 counts 1+2+2+2+2+2+2= 1+1+1+2+2+2+6.
a(16)=3 counts 2+2+2+2+2+2+2+2 = 1+1+2+2+2+2+6 = 1+1+1+1+6+6.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Giovanni Resta)
J. Wang, Reduced phi-partitions of positive integers, Fib. Quart. 31 (4) (1993) 365-369.
J. Wang, X. Wang, On the set of reduced phi-partitions of a positive integer, Fib. Quart. 44 (2) (2006) 98-102.

Cf. A283528, A283529, A283320.

isA002110 := proc(n)
    member(n,[1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810, 304250263527210, 13082761331670030, 614889782588491410, 32589158477190044730, 1922760350154212639070]) ;
end proc:
A283530 := proc(n)
    local a,k,issimp,p ;
    a := 0 ;
    for k in combinat[partition](n) do
        issimp := true ;
        for p in k do
            if not isA002110(p) then
                issimp := false;
                break;
            end if;
        end do:
        if issimp and nops(k) > 1 then
            phip := add(numtheory[phi](p),p=k) ;
            if phip = numtheory[phi](n) then
                a := a+1 ;
            end if;
        end if;
    end do:
    a ;
end proc:

v={1,2,6,30,210}; e=10^9 v + EulerPhi@v; a[n_] := Length@ IntegerPartitions[ 10^9 n + EulerPhi[n], {2, Infinity}, e]; Array[a, 100] (* suitable for n <= 1000, Giovanni Resta, Mar 10 2017 *)

a(A002110(k)) = 0. [Wang]

A283320 Composite semisimple numbers.

Original entry on oeis.org

4, 9, 10, 12, 18, 24, 42, 60, 84, 90, 120, 150, 180, 330, 390, 420, 630, 840, 1050, 1260, 1470, 1680, 1890, 2100, 2730, 3570, 3990, 4620, 5460, 6930, 8190, 9240, 10920, 11550, 13650, 13860, 16170, 18480, 20790, 23100, 25410, 27720, 39270, 43890, 53130

Offset: 1

N. J. A. Sloane, Mar 13 2017

nonn

See A283530 for the definition of semisimple numbers, and A283736 for the full list.

The term a(94) = A002110(9)/prime(7) is the smallest term larger than some A002110(i+1) without being a multiple of the next smaller primorial A002110(i), here with i=7. For subsequent terms of the form a(n) = A002110(i+2)/prime(i), the ratio a(n)/A002110(i+1) = prime(i+2)/prime(i) is smaller, but one can have a multiple m*a(n) of such a term, provided m*(prime(i+2)-(prime(i))(prime(i+1)-prime(i)) < prime(i). This occurs first at a(419) = 2*a(405) and a(425) = 3*a(405) with a(405) = A002110(15)/prime(13) ~ 1.5e16. No term > 4*p# not a multiple of (p-1)# occurs below 4*79#/71 ~ 1.8e29, and no term > 5*p# not a multiple of (p-1)# occurs below 5*107#/101 ~ 1.3e41. The first term of the form A002110(i+3)/prime(i) also appears for prime(i) = 101. - M. F. Hasler, Mar 16 2017

M. F. Hasler, Table of n, a(n) for n = 1..500 (Terms up to 3.5*10^18.)
J. Wang, X. Wang, On the set of reduced phi-partitions of a positive integer, Fib. Quart. 44 (2) (2006) 98-102.

Cf. A283528, A283530, A283736.

is_A283320(n)={bittest(n,0)&&return(n==9);(2>n\=2)&&return;my(Q,m);forprime(p=3,,np && for(k=1, #Q-m=#select(q->q<=p, Q), forvec(q=vector(k, j, [m+1, #Q]), prod(i=1, k, 1-p/Q[q[i]], n)M. F. Hasler, Mar 15 2017

list_A283320(n,L=4,N=1,s=1,a=List())={forprime(p=2,,L*=nextprime(p+1);until(N>=L,until(is_A283320(N+=s),);listput(a,N);n--||return(Vec(a)));s*=p)} \\ Assumes the gap is a multiple of (p-1)# for N >= (L/2)*p#: With the default L=4, the step is increased to s = 2, 6, 30,... for N >= 12, 60, 420,... For n > 418 one must increase L, since a(419) = 2*A002110(15)/prime(13) ~ 2.3*A002110(14) and a(425) = 3*A002110(15)/prime(13) ~ 3.4*A002110(14) are not multiples of A002110(13). No other such term > 2*p# not a multiple of (p-1)# occurs below 2*67#/59 ~ 2.7e23, and L=8 is sufficient up to 4*73#/71 = 1.8e29. - M. F. Hasler, Mar 16 2017

a(19)-a(32) from Alois P. Heinz, Mar 15 2017

a(33) and beyond from M. F. Hasler, Mar 17 2017

A283529 The number of partitions of n into simple parts.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 9, 9, 12, 12, 15, 15, 18, 18, 22, 22, 26, 26, 30, 30, 35, 35, 40, 40, 45, 45, 52, 52, 59, 59, 66, 66, 75, 75, 84, 84, 93, 93, 104, 104, 115, 115, 126, 126, 139, 139, 152, 152, 165, 165, 180, 180, 195, 195, 210, 210, 228, 228

Offset: 0

R. J. Mathar, Mar 10 2017

nonn

Number of partitions of n where each part is simple, meaning that each part is in A002110.

			a(6)=5 counts 1+1+1+1+1+1 = 1+1+1+2 = 1+1+2+2 = 2+2+2 =6.
a(7)=5 counts 1+1+1+1+1+1+1 = 1+1+1+1+1+2 = 1+1+1+2+2 = 1+2+2+2 = 1+6.

Giovanni Resta, Table of n, a(n) for n = 0..10000
J. Wang, Reduced phi-partitions of positive integers, Fib. Quart. 31 (4) (1993) 365-369.

Cf. A002110, A064986, A283528.

isA002110 := proc(n)
    member(n,[1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810, 304250263527210, 13082761331670030, 614889782588491410, 32589158477190044730, 1922760350154212639070]) ;
end proc:
A283529 := proc(n)
    local a,k,issimp,p ;
    a := 0 ;
    for k in combinat[partition](n) do
        issimp := true ;
        for p in k do
            if not isA002110(p) then
                issimp := false;
                break;
            end if;
        end do:
        if issimp then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:

(* It suffices to compute 3 primorials to get 100 correct terms *)
terms = 100; primorials = FoldList[Times, 1, Prime[Range[3]]]; 1/(Times @@ (1 - x^primorials)) + O[x]^terms // CoefficientList[#, x]& (* Jean-François Alcover, May 19 2018 *)

G.f.: 1/Product_{i>=0} (1-x^A002110(i)).

a(0)=1 prepended by Alois P. Heinz, Mar 13 2017

A283736 Semisimple numbers: positive integers having exactly one reduced phi-partition.

Original entry on oeis.org

3, 4, 5, 7, 9, 10, 11, 12, 13, 17, 18, 19, 23, 24, 29, 31, 37, 41, 42, 43, 47, 53, 59, 60, 61, 67, 71, 73, 79, 83, 84, 89, 90, 97, 101, 103, 107, 109, 113, 120, 127, 131, 137, 139, 149, 150, 151, 157, 163, 167, 173, 179, 180, 181, 191, 193, 197

Offset: 1

M. F. Hasler, Mar 15 2017

nonn

A phi-partition of n is a sum x_1 + ... + x_r = n, 1 <= x_1 <= ... <= x_r with r > 1, such that phi(x_1) + ... + phi(x_r) = phi(n), where phi = A000010 is Euler's totient function.
A partition is reduced iff each summand is a primorial number A002110(k) = product of the first k primes, k >= 0.
It is known that semisimple numbers are the union of odd primes, {9} and numbers of the form n = a*q_1*...q_k*A002110(i) with k >= 0, i >= 1, q_1 > ... > q_k > p := prime(i+1) > a*(q_1-p)*...*(q_k-p), see examples.

			As said in comments, this sequence contains the odd primes A065091, 9, and elements of A060735: multiples of primorials A002110 not larger than the next primorial, except for the primorials themselves. These could be called trivial solutions and include all numbers up to 13 except for 1, 2, 6 (primorials), 8 (not semisimple) and 10 (semisimple, see below).
Let us call nontrivial the terms that can only be written in the form a*q_1*...*q_k*A002110(i) with k >= 1. It will be convenient to write A002110(i) as (p-1)# := A034386(p-1) with p := prime(i+1).
In the case k=1, we have multiples n = a q (p-1)# such that a*(q - p) < p.
Here, a = 1 and q = prime(i+2) always yields a solution (since prime(i+2) < 2 prime(i+1) for all i), so these could also be considered as "trivial" solutions.
For i = 1, p = 3 > a*(q-3) has only this "trivial" solution, a = 1, q = 5, n = 5*2 = 10 = a(9).
For i = 2, p = 5 > a*(q-5) for q = 7, a = 1, n = 7*3*2 = 42 ("trivial") and a = 2, n = 2*7*6 = 84, no other solution with q > 7, i.e., q >= 11.
For i = 3, p = 7 > a*(q-7) has solutions q = 11, a = 1, n = 11*5*3*2 ("trivial"), and q = 13, a = 1 : n = 13*5# = 390.
For i = 4, p = 11 > a*(q - 11) has solutions:
   q = 13, a = 1,2,3,4,5 : n = a*13*7# = a*2730, and
   q = 17 and 19, a = 1 : n = 17*7# = 3570  and n = 19*7# = 3990.
Concerning the solutions with k=2, one can easily check that (prime(i+2)-prime(i+1))*(prime(i+3)-prime(i+1)) < prime(i+1) for i >= 6 but not i = 7, 8, 10, 14, 22, 23, 29, 45. Thus, prime(i+2)*prime(i+3)*A002110(i) = A002110(i+3)/prime(i+1) is a solution for all these values of i, the smallest term of this form being prime(8)*prime(9)*prime(6)# = prime(9)# / prime(7) = 13123110.

Jun Wang and Xin Wang, On the set of reduced φ-partitions of a positive integer, Fibonacci Quarterly 44, no. 2 (May 2006), p. 98

Cf. A002110, A034386, A060735, A283528, A283530.

See A283320 for the composite semisimple numbers.

is_semisimple(n,Q,m)={if(bittest(n,0),isprime(n)||n==9,n\=2;forprime(p=3,,np && for(k=1,#Q-m=#select(q->q<=p,Q),forvec(q=vector(k,j,[m+1,#Q]),prod(i=1,k,1-p/Q[q[i]],n)0, p and the indices [ i_1 ... i_k ] such that q_m is the ( i_m )-th prime factor of n/(p-1)#.

A284114 Number of partitions of n such that Omega(n) (= number of prime divisors of n counted with multiplicity) equals the sum of Omega of all parts; Omega = A001222.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 5, 4, 7, 9, 12, 5, 22, 6, 17, 19, 55, 7, 50, 8, 60, 28, 32, 9, 166, 37, 41, 113, 122, 10, 137, 11, 631, 51, 56, 57, 475, 12, 64, 66, 620, 13, 258, 14, 282, 301, 83, 15, 2229, 90, 359, 95, 394, 16, 1302, 105, 1435, 109, 114, 17, 1708, 18, 125

Offset: 0

Alois P. Heinz, Mar 20 2017

nonn

			a(5) = 3: [2,1,1,1], [3,1,1], [5].
a(6) = 5: [2,2,1,1], [3,2,1], [3,3], [4,1,1], [6].
a(7) = 4: [2,1,1,1,1,1], [3,1,1,1,1], [5,1,1], [7].
a(8) = 7: [2,2,2,1,1], [3,2,2,1], [3,3,2], [4,2,1,1], [4,3,1], [6,2], [8].
a(9) = 9: [2,2,1,1,1,1,1], [3,2,1,1,1,1], [3,3,1,1,1], [4,1,1,1,1,1], [5,2,1,1], [5,3,1], [6,1,1,1], [7,2], [9].
a(10) = 12: [2,2,1,1,1,1,1,1], [3,2,1,1,1,1,1], [3,3,1,1,1,1], [4,1,1,1,1,1,1], [5,2,1,1,1], [5,3,1,1], [5,5], [6,1,1,1,1], [7,2,1], [7,3], [9,1], [10].

Alois P. Heinz, Table of n, a(n) for n = 0..6000
Wikipedia, Partition (number theory)

Cf. A000040, A000041, A000720, A001222, A283528.

with(numtheory):
b:= proc(n, i, m) option remember; `if`(n=0 or i=1,
      `if`(m=0, 1, 0), `if`(m<0, 0, b(n, i-1, m)+
      `if`(i>n, 0, b(n-i, i, m-bigomega(i)))))
    end:
a:= n-> b(n$2, bigomega(n)):
seq(a(n), n=0..80);

b[n_, i_, m_] := b[n, i, m] = If[n == 0 || i == 1, If[m == 0, 1, 0], If[m < 0, 0, b[n, i-1, m] + If[i>n, 0, b[n-i, i, m - PrimeOmega[i]]]]];
a[0] = 1; a[n_] := b[n, n, PrimeOmega[n]];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Mar 25 2017, translated from Maple *)

b(n, i, m) = if(n==0 || i==1, if(m==0, 1, 0), if(m<0, 0, b(n, i - 1, m) + if(i>n, 0, b(n - i, i, m - bigomega(i)))));
a(n) = if(n<1, 1, b(n, n, bigomega(n)));
for(n=0, 80, print1(a(n),", ")) \\ Indranil Ghosh, Mar 25 2017, translated from Mathematica

a(p) = A000720(p) for prime p.

cp's OEIS Frontend

A283530 The number of reduced phi-partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A283320 Composite semisimple numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Extensions

A283529 The number of partitions of n into simple parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A283736 Semisimple numbers: positive integers having exactly one reduced phi-partition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A284114 Number of partitions of n such that Omega(n) (= number of prime divisors of n counted with multiplicity) equals the sum of Omega of all parts; Omega = A001222.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula