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,6

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

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

Formula

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

Example

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

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 *)

Prog

(PARI) a(n)=my(i=1, j, f, c, t, s); while((f=fibonacci(i++))<n, t=n-f; j=0; while((c=binomial(2*j++, j)/(j+1))<t-2, s+=isprime(t-c))); s \\ Charles R Greathouse IV, Nov 22 2011

Crossrefs

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

Sequence in context: A064631 A347293 A113730 * A225577 A265531 A083662

Adjacent sequences: A154401 A154402 A154403 * A154405 A154406 A154407

Keyword

nice,nonn

Author

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

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

Status

approved