login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A283736 Semisimple numbers: positive integers having exactly one reduced phi-partition. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..57.

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

EXAMPLE

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 A002210(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.

PROG

(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)#.

CROSSREFS

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

See A283320 for the composite semisimple numbers.

Sequence in context: A155935 A081606 A079945 * A039017 A275319 A285343

Adjacent sequences:  A283733 A283734 A283735 * A283737 A283738 A283739

KEYWORD

nonn

AUTHOR

M. F. Hasler, Mar 15 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 12 03:14 EDT 2021. Contains 342912 sequences. (Running on oeis4.)