A233544 Number of ways to write n = k^2 + m with k > 0 and m >= k^2 such that sigma(k^2) + phi(m) is prime, where sigma(k^2) is the sum of all (positive) divisors of k^2, and phi(.) is Euler's totient function (A000010).

0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 1, 3, 2, 2, 2, 2, 2, 1, 1, 2, 3, 2, 1, 2, 1, 2, 2, 1, 2, 2, 2, 4, 3, 2, 3, 2, 3, 4, 2, 1, 3, 3, 3, 4, 2, 2, 2, 3, 1, 5, 4, 2, 4, 2, 4, 3, 2, 4, 4, 2, 3, 3, 2, 1, 4, 2, 3, 6, 2, 5, 3, 5, 3, 4, 3, 3, 4, 4, 2, 2, 5, 2, 3, 5, 3, 4, 2, 2, 4, 3, 3, 5, 6, 3

Offset

1,9

Comments

Conjectures:

(i) a(n) > 0 for all n > 1.

(ii) Any integer n > 1 can be written as k + m with k > 0 and m > 0 such that sigma(k)^2 + phi(m) (or sigma(k) + phi(m)^2) is prime.

Part (i) of the conjecture is stronger than the conjecture in A232270. We have verified it for n up to 10^8.

I verified the conjecture to 3*10^9. The conjecture is almost surely true. - Charles R Greathouse IV, Dec 13 2013

There are no counterexamples to conjecture (i) < 5.12 * 10^10. - Jud McCranie, Jul 23 2017

The conjectures appeared as Conjecture 3.31 in the linked 2017 paper. - Zhi-Wei Sun, Nov 30 2018

Links

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641 [math.NT], 2014.

Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv:1211.1588 [math.NT], 2012-2017.)

Example

a(10) = 1 since 10 = 1^2 + 9 with sigma(1^2) + phi(9) = 1 + 6 = 7 prime.
a(25) = 1 since 25 = 2^2 + 21 with sigma(2^2) + phi(21) = 7 + 12 = 19 prime.
a(34) = 1 since 34 = 4^2 + 18 with sigma(4^2) + phi(18) = 31 + 6 = 37 prime.
a(46) = 1 since 46 = 2^2 + 42 with sigma(2^2) + phi(42) = 7 + 12 = 19 prime.
a(106) = 1 since 106 = 3^2 + 97 with sigma(3^2) + phi(97) = 13 + 96 = 109 prime.
a(163) = 1 since 163 = 3^2 + 154 with sigma(3^2) + phi(154) = 13 + 60 = 73 prime.
a(265) = 1 since 265 = 11^2 + 144 with sigma(11^2) + phi(144) = 133 + 48 = 181 prime.
a(1789) = 1 since 1789 = 1^2 + 1788 with sigma(1^2) + phi(1788) = 1 + 592 = 593 prime.
a(1157) = 3, since 1157 = 10^2 + 1057 with sigma(10^2) + phi(1057) = 217 + 900 = 1117 prime, 1157 = 21^2 + 716 with sigma(21^2) + phi(716) = 741 + 356 = 1097 prime, and 1157 = 24^2 + 581 with sigma(24^2) + phi(581) = 1651 + 492 = 2143 prime. In this example, none of 10, 21 and 24 is a prime power.

Mathematica

sigma[n_]:=Sum[If[Mod[n, d]==0, d, 0], {d, 1, n}]
a[n_]:=Sum[If[PrimeQ[sigma[k^2]+EulerPhi[n-k^2]], 1, 0], {k, 1, Sqrt[n/2]}]
Table[a[n], {n, 1, 100}]

Prog

(PARI) a(n)=sum(k=1, sqrtint(n\2), isprime(sigma(k^2)+eulerphi(n-k^2))) \\ Charles R Greathouse IV, Dec 12 2013

Crossrefs

Cf. A000010, A000040, A000203, A000290, A220272, A232270, A230494.

Sequence in context: A108461 A321004 A258595 * A026535 A080462 A194823

Adjacent sequences: A233541 A233542 A233543 * A233545 A233546 A233547

Keyword

nonn

Author

Zhi-Wei Sun, Dec 12 2013

Status

approved