[seqfan] Re: phi-partitions of n

[M. F. Hasler]

On Thu, Mar 9, 2017 at 1:55 PM, Neil Sloane wrote:

> Dear Seq Fans, Call a partition n = a1+...+ak  a phi-partition
> if phi(n) = phi(a1)+...+phi(ak), where phi() = A10().
> There are several refinements, such as reduced phi-partitions.
> Are these sequences (the number of ... of n) in the OEIS?
> Also the related sequence of semisimple integers (Wang and Wang)

- it seems the smallest is 746130, so this is definitely not yet in the
> OEIS - how does it continue?
>

Actually, the cited paper,
http://www.fq.math.ca/Papers1/44-2/quartwang02_2006.pdf
show that 746130 is *not* semisimple, by listing its reduced phi-partitions.
Then it says that  p9*p8*A6 (= prime(9)# / prime(7) = 13123110)
is the smallest semisimple integer
* *of the given form, **with a = 1 and k >= 2 **.

The "given form" is   n = a  q_1 ... q_k A_i ,  where:
  A_i = product( prime(j), j <= i ) = A002110 <https://oeis.org/A002110>(i),
i >= 1,
  the q's are  k >= 0  distinct primes > P := prime( i+1 ), and
  a is a positive integer such that  a (q_1 - P) ... (q_k - P) < P

If we take k=0 there is no constraint except a < P.
So, in addition to 9 and all primes which are also semisimple, all
multiples of the primorials A_i less than P*A_i = A_{i+1} are also
semisimple.
These are
1,2,4,6,12,18,24,30,60,90,120,150,180,210,420,630,840,... =
A060735 <https://oeis.org/A060735> :
Where n / (phi(n) + 1) increases.
(... this sequence is a primorial (A002110 <https://oeis.org/A002110>)
followed by its multiples until the next primorial, then the multiples of
that primorial and so on.)

If we add the primes and 9, we get
12,3,4,5,6,7,9,11,12,13,17,18,19,23,24,29,30,31,37,41,43,47,53,59,60,61,67,
71,73,79,83,89,90,97,101,103,107,109,113,120,127,131,137,139,149,150,...
which seems not in the OEIS.

We could call "nontrivial" the semisimple integers not of this form,
i.e., which can only be written in the given form with k >= 1.

In the case k=1, we have multiples n = a q A_i such that  a*(q - P) < P :=
prime(i+1).
As the paper states, a = 1, 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. They include n = 5*2 = 10, 7*3*2 = 42,
11*5# = 330, ...

The first "strictly nontrivial" solutions are:
For i = 2, P = 5 > a*(q-5) with q = 7, a = 2: n = 2*7*3*2 = 84.
For i = 3, P = 7 > a*(q-7) with q = 13, a = 1: n = 1*13*5# = 390.
For i = 4, P = 11 > a*(q - 11) with
 q = 13, a = 2,3,4,5 ; n = a*13*7# = a*2730
 q = 17 and 19, a = 1 : n = 17*7# = 3570  and n = 19*7# = 3990.

There are many more solutions before the first solutions with k=2.
Concerning these, one can easily check that
 (prime(i+2)-prime(i+1))*(prime(i+3)-prime(i+1)) < prime(i+1)
only for  i >= 6 (but not for i=7,8,10,14,22,23,29,45),
so  prime(8)*prime(9)*prime(6)# = prime(9)# / prime(7) is indeed the
smallest *of this form*.
I have submitted the set of all semisimple integers as
https://oeis.org/draft/A283736/.
Since they are quite dense (8, 14, 15, 16 are the only missing numbers
below 20),
I could also submit the subset of nontrivial (or "strictly nontrivial")
solutions, if other editors agree.

PS: I hope all SeqFans had a nice pi-day!

-Maximilian