A154404 Number of ways to express n as the sum of an odd prime, a positive Fibonacci number and a Catalan number.

0, 0, 0, 0, 1, 2, 3, 3, 5, 5, 5, 4, 6, 5, 6, 5, 7, 6, 6, 9, 9, 8, 8, 6, 8, 10, 9, 6, 9, 7, 5, 8, 10, 8, 8, 7, 6, 9, 9, 8, 8, 7, 6, 9, 9, 13, 10, 9, 8, 12, 10, 10, 10, 9, 9, 11, 9, 11, 9, 10, 8, 11, 13, 11, 10, 12, 11, 11, 10, 10, 7, 8, 10, 14, 10, 16, 11, 9, 11, 11, 10, 12, 10, 7, 9, 16, 10, 12

Offset: 1

Author

Qing-Hu Hou (hou(AT)nankai.edu.cn), Jan 09 2009, Jan 18 2009

Keywords

• nice
• nonn

Comments

Motivated by Zhi-Wei Sun's conjecture that each integer n>4 can be expressed as the sum of an odd prime, an odd Fibonacci number and a positive Fibonacci number (cf. A154257), during their visit to Nanjing Univ. Qing-Hu Hou (Nankai Univ.) and Jiang Zeng (Univ. of Lyon-I) conjectured on Jan 09 2009 that a(n)>0 for every n=5,6,.... and verified this up to 5*10^8. D. S. McNeil has verified the conjecture up to 5*10^13 and Hou and Zeng have offered prizes for settling their conjecture (see Sun 2009).

Examples

			For n=7 the a(7)=3 solutions are 3+2+2, 3+3+1, 5+1+1.
		

References

• R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36(1971), 103-107.
• R. P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge Univ. Press, 1999, Chapter 6.

Links

• Jon E. Schoenfield, Table of n, a(n) for n = 1..100000
• D. S. McNeil, Sun's strong conjecture
• Zhi-Wei Sun, A promising conjecture: n=p+F_s+F_t
• Zhi-Wei Sun, A summary concerning my conjecture n=p+F_s+F_t (II)
• Z.-W. Sun and R. Tauraso, Congruences involving Catalan numbers, arXiv:0709.1665v5.
• Zhi-Wei Sun, Mixed sums of primes and other terms, preprint, 2009

Crossrefs

Cf. A000040, A000045, A000108, A154257, A154290, A154285, A154952, A156695.

Programs

Maple

Cata:=proc(n) binomial(2*n,n)/(n+1); end proc: Fibo:=proc(n) if n=1 then return(1); elif n=2 then return(2); else return(Fibo(n-1) + Fibo(n-2)); fi; end proc: for n from 1 to 10^3 do rep_num:=0; for i from 1 while Fibo(i) < n do for j from 1 while Fibo(i)+Cata(j) < n do p:=n-Fibo(i)-Cata(j); if (p>2) and isprime(p) then rep_num:=rep_num+1; fi; od; od; printf("%d %d\n", n, rep_num); od:

Mathematica

a[n_] := (pp = {}; p = 2; While[ Prime[p] < n, AppendTo[pp, Prime[p++]] ]; ff = {}; f = 2; While[ Fibonacci[f] < n, AppendTo[ff, Fibonacci[f++]]]; cc = {}; c = 1; While[ CatalanNumber[c] < n, AppendTo[cc, CatalanNumber[c++]]]; Count[Outer[Plus, pp, ff, cc], n, 3]); Table[a[n], {n, 1, 88}] (* Jean-François Alcover, Nov 22 2011 *)

PARI

a(n)=my(i=1,j,f,c,t,s);while((f=fibonacci(i++))Charles R Greathouse IV, Nov 22 2011

Formula

a(n) = |{: p+F_s+C_t=n with p an odd prime and s>1}|.

Extensions

More terms from Jon E. Schoenfield, Jan 17 2009

Added the new verification record and Hou and Zeng's prize for settling the conjecture. Edited by Zhi-Wei Sun, Feb 01 2009

Comment edited by Charles R Greathouse IV, Oct 28 2009