A233544 - OEIS

%I #38 Dec 06 2018 12:07:46

%S 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,

%T 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,

%U 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

%N 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).

%C Conjectures:

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

%C (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.

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

%C I verified the conjecture to 3*10^9. The conjecture is almost surely true. - _Charles R Greathouse IV_, Dec 13 2013

%C There are no counterexamples to conjecture (i) < 5.12 * 10^10. - _Jud McCranie_, Jul 23 2017

%C The conjectures appeared as Conjecture 3.31 in the linked 2017 paper. - _Zhi-Wei Sun_, Nov 30 2018

%H Zhi-Wei Sun, <a href="/A233544/b233544.txt">Table of n, a(n) for n = 1..10000</a>

%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1402.6641">Problems on combinatorial properties of primes</a>, arXiv:1402.6641 [math.NT], 2014.

%H Zhi-Wei Sun, <a href="https://doi.org/10.1007/978-3-319-68032-3_20">Conjectures on representations involving primes</a>, 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 <a href="http://arxiv.org/abs/1211.1588">arXiv:1211.1588 [math.NT]</a>, 2012-2017.)

%e a(10) = 1 since 10 = 1^2 + 9 with sigma(1^2) + phi(9) = 1 + 6 = 7 prime.

%e a(25) = 1 since 25 = 2^2 + 21 with sigma(2^2) + phi(21) = 7 + 12 = 19 prime.

%e a(34) = 1 since 34 = 4^2 + 18 with sigma(4^2) + phi(18) = 31 + 6 = 37 prime.

%e a(46) = 1 since 46 = 2^2 + 42 with sigma(2^2) + phi(42) = 7 + 12 = 19 prime.

%e a(106) = 1 since 106 = 3^2 + 97 with sigma(3^2) + phi(97) = 13 + 96 = 109 prime.

%e a(163) = 1 since 163 = 3^2 + 154 with sigma(3^2) + phi(154) = 13 + 60 = 73 prime.

%e a(265) = 1 since 265 = 11^2 + 144 with sigma(11^2) + phi(144) = 133 + 48 = 181 prime.

%e a(1789) = 1 since 1789 = 1^2 + 1788 with sigma(1^2) + phi(1788) = 1 + 592 = 593 prime.

%e 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.

%t sigma[n_]:=Sum[If[Mod[n,d]==0,d,0],{d,1,n}]

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

%t Table[a[n],{n,1,100}]

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

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

%K nonn

%O 1,9

%A _Zhi-Wei Sun_, Dec 12 2013