A283528
The number of phi-partitions of n.
Original entry on oeis.org
0, 0, 1, 1, 2, 0, 3, 4, 8, 2, 4, 1, 5, 8, 24, 24, 6, 2, 7, 15, 107, 46, 8, 4, 135, 101, 347, 83, 9, 0, 10, 460, 1019, 431, 1308, 13, 11, 842, 2760, 214, 12, 2, 13, 1418, 5124, 2977, 14, 42, 2021, 720, 17355, 4997, 15, 70, 21108, 3674, 40702, 16907, 16, 1, 17
Offset: 1
a(7) = 3 counts the partitions 1+1+1+1+1+2 = 1+1+1+1+3 = 1+1+5.
a(8) = 4 counts the partitions 2+2+2+2 = 2+2+4 = 4+4 = 1+1+6.
-
A283528 := proc(n)
local a,k,phip ;
a := 0 ;
for k in combinat[partition](n) do
if 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:
# second Maple program:
with(numtheory):
b:= proc(n, m, i) option remember; `if`(n=0,
`if`(m=0, 1, 0), `if`(i<1 or m<0, 0, b(n, m, i-1)+
`if`(i>n, 0, b(n-i, m-phi(i), i))))
end:
a:= n-> b(n, phi(n), n)-1:
seq(a(n), n=1..70); # Alois P. Heinz, Mar 10 2017
-
Table[ Length@ IntegerPartitions[n 10^7 + EulerPhi[n], {2, Infinity},
EulerPhi@ Range[n-1] + 10^7 Range[n-1]], {n, 60}] (* Giovanni Resta, Mar 10 2017 *)
b[n_, m_, i_] := b[n, m, i] = If[n == 0,
If[m == 0, 1, 0], If[i < 1 || m < 0, 0, b[n, m, i - 1] +
If[i > n, 0, b[n - i, m - EulerPhi[i], i]]]];
a[n_] := b[n, EulerPhi[n], n]-1;
Array[a, 70] (* Jean-François Alcover, Jun 01 2021, after Alois P. Heinz *)
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
-
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
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
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.
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)#.
Showing 1-3 of 3 results.
Comments