cp's OEIS Frontend

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

%I A283736 #21 Jan 05 2025 19:51:41
%S A283736 3,4,5,7,9,10,11,12,13,17,18,19,23,24,29,31,37,41,42,43,47,53,59,60,
%T A283736 61,67,71,73,79,83,84,89,90,97,101,103,107,109,113,120,127,131,137,
%U A283736 139,149,150,151,157,163,167,173,179,180,181,191,193,197
%N A283736 Semisimple numbers: positive integers having exactly one reduced phi-partition.
%C A283736 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.
%C A283736 A partition is reduced iff each summand is a primorial number A002110(k) = product of the first k primes, k >= 0.
%C A283736 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.
%H A283736 Jun Wang and Xin Wang, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/44-2/quartwang02_2006.pdf">On the set of reduced φ-partitions of a positive integer</a>, Fibonacci Quarterly 44, no. 2 (May 2006), p. 98
%e A283736 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).
%e A283736 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).
%e A283736 In the case k=1, we have multiples n = a q (p-1)# such that a*(q - p) < p.
%e A283736 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.
%e A283736 For i = 1, p = 3 > a*(q-3) has only this "trivial" solution, a = 1, q = 5, n = 5*2 = 10 = a(9).
%e A283736 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.
%e A283736 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.
%e A283736 For i = 4, p = 11 > a*(q - 11) has solutions:
%e A283736    q = 13, a = 1,2,3,4,5 : n = a*13*7# = a*2730, and
%e A283736    q = 17 and 19, a = 1 : n = 17*7# = 3570  and n = 19*7# = 3990.
%e A283736 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.
%o A283736 (PARI) is_semisimple(n,Q,m)={if(bittest(n,0),isprime(n)||n==9,n\=2;forprime(p=3,,n<p&&return(n-1); Q=factor(n)[,1]; Q[#Q]>p && 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)<p&&return([p,q]),2));n%p && return;n\=p))} \\ if n = a*q_1*...*q_k*(p-1)# is semisimple, return a-1 if k=0, or if k>0, p and the indices [ i_1 ... i_k ] such that q_m is the ( i_m )-th prime factor of n/(p-1)#.
%Y A283736 Cf. A002110, A034386, A060735, A283528, A283530.
%Y A283736 See A283320 for the composite semisimple numbers.
%K A283736 nonn
%O A283736 1,1
%A A283736 _M. F. Hasler_, Mar 15 2017