A306771 Numbers m such that m = i + j = i * k and phi(m) = phi(i) + phi(j) = phi(i) * phi(k) for some i, j, k, where phi is the Euler totient function A000010.

3, 15, 21, 33, 39, 51, 57, 69, 75, 87, 93, 105, 111, 123, 129, 141, 147, 159, 165, 177, 183, 195, 201, 213, 219, 231, 237, 249, 255, 267, 273, 285, 291, 303, 309, 321, 327, 339, 345, 357, 363, 375, 381, 393, 399, 411, 417, 429, 435, 447, 453, 465, 471, 483, 489

Offset: 1

Author

Michel Lagneau, Mar 09 2019

Keywords

• nonn
• easy

Comments

The 55 terms given in the data section are consistent with a definition "numbers congruent to 3 or 15 mod 18". - Peter Munn, May 12 2020

The observation above is true for the first 10^4 terms. - Amiram Eldar, Dec 08 2020

The observation above is true for every term; see link. - Flávio V. Fernandes, Apr 18 2022

A001748 \ {6, 9} is a subsequence because, for p prime >= 5, 3 * p = p + 2p = p * 3 and phi(3p) = phi(p) + phi(2p) = phi(p) * phi(3) = 2 * (p-1). - Bernard Schott, May 13 2022

Examples

			33 is in the sequence because:
phi(33) = phi(11 + 22) = phi(11) + phi(22) = 10 + 10 = 20, and
phi(33) = phi(3 * 11) = phi(3) * phi(11) = 2 * 10 = 20.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Flávio V. Fernandes, A306771(n) equals 3 times A007310(n)
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Crossrefs

Cf. A000010, A000040, A007310, A001748, A381671.

Programs

Maple

with(numtheory):
for n from 1 to 500 do:
ii:=0:
  for i from 1 to trunc(n/2) while(ii=0) do:
   if phi(i)+ phi(n-i)= phi(n) and n/i = floor(n/i)
      and phi(i)*phi(n/i)=phi(n)
      then
      ii:=1:printf(`%d, `,n):
      else
   fi:
  od:
od:

Mathematica

LinearRecurrence[{1, 1, -1}, {3, 15, 21}, 100] (* Paolo Xausa, Mar 07 2025 *)

PARI

isok(m) = {my(phim = eulerphi(m)); for (i=1, m\2, if ((eulerphi(i) + eulerphi(m-i) == phim) && !frac(m/i) && (eulerphi(m/i)*eulerphi(i) == phim), return (1)););} \\ Michel Marcus, Mar 09 2019

Formula

From Chai Wah Wu, Mar 07 2025: (Start)

a(n) = a(n-1) + a(n-2) - a(n-3) for n > 3.

G.f.: x*(3*x^2 + 12*x + 3)/((x - 1)^2*(x + 1)). (End)

Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/(6*sqrt(3)) (A381671). - Amiram Eldar, Mar 08 2025

Extensions

Incorrect comment deleted by Peter Munn, May 12 2020

Name corrected by Flávio V. Fernandes, Aug 26 2021 and Peter Munn, Sep 03 2021