Does for every integer $k$ exist a positive integer $n$ such that $F_n+k$ is prime

elementary-number-theoryfibonacci-numbersfunctionsprime numbers

For an integer $k$ , define $f(k)$ to be the smallest positive integer $n$ such that $F_n+k$ is prime (where $F_n$ denotes the $n$-th Fibonacci number) , if such an $n$ exists and undefined else.

Is $f(k)$ total , in other words , does always such a positive integer $n$ exist no matter what $k$ is ?

The $152$ "tough cases " in the range $[-10^5,10^5]$ (no prime for $n\le 10^4$) are :

-96715 -95551 -93963 -93439 -92293 -90791 -90119 -89607 -88817 -85723
-85445 -85343 -83733 -82697 -81635 -81037 -81005 -78035 -77741 -77397
-77313 -76851 -76519 -75977 -75923 -75089 -74995 -74919 -74273 -74129
-73893 -72665 -72183 -71921 -71535 -71469 -71315 -70967 -69983 -69873
-69411 -67367 -67123 -66929 -64163 -63633 -62677 -62531 -62407 -61277
-60979 -59753 -59219 -58533 -58269 -57885 -57401 -57103 -55811 -55097
-53145 -52603 -52277 -52221 -52193 -50567 -50447 -48841 -47217 -46905
-46903 -45839 -44589 -43981 -43537 -41743 -40681 -40649 -39591 -38097
-36805 -36803 -36323 -35957 -35929 -34971 -30345 -28965 -25145 -23695
-23163 -22707 -22023 -21813 -20617 -20147 -20077 -18717 -15471 -15067
-12333 -12123 -12061 -11649 -11643 -11441 -9919 -9341 -9087 -7505
-5151 -4115 6313 6851 7123 10591 11009 11561 13651 14475
19391 23843 25753 27727 27871 30282 30547 32053 33813 43711
45165 49351 53227 62177 64617 65953 66669 68149 69541 74325
74397 75249 78625 78693 85447 86085 88487 93687 93763 94485
94979 97945

I think , small factors are not forced , no matter what $k$ is and considering the grwoth rate of $F_n$ (just exponential) , we can expect the existence of infinite many $n$ for every $k$

Best Answer

No, $f(k)$ is not total.

Reference https://oeis.org/A361902 for $k\ge 0$, where it states that if $k\equiv 14475 \pmod {1647030}$ then there is no solution.

The OEIS page links to a proof by Robert Gerbicz here.

Set T=2*3*5*7*11*23*31=1647030, then the Fibonacci sequence is periodic mod
T using period=240.
So need to check only the first 240 Fibonacci numbers, and for
each of them T and 14475+fibonacci(k) is not coprime, and of course bigger
than 31, so 14475+fibonacci(k) is composite for the first 240 k values, but
then for every k.

It also states that currently the solutions for $f(7123)$ and $f(11009)$ are unknown and are at least $F_{60000}$ (and, per the question, now checked to $F_{100000}$).

https://oeis.org/A322004 is the equivalent for $k\le 0$.

Related Question