I've been working on this all night, and I have made this go pretty fast, compared to my first iteration of the program, but now I'm out of ideas.
I'm trying to write a program to test (by good old fashioned brute force) if there is a composite positive integer $n \equiv 3 \pmod {10}$ or $n \equiv 7 \pmod {10}$ where $n$ is a Fermat Pseudoprime, and $n$ divides the $n+1^{\rm th}$ Fibonacci number.
Here is what I have so far:
$HistoryLength = 5; startingIter = 0; iters = startingIter;
listLength = 10000; maxIters = 20;
nextBlock[start_, listlength_] := Block[
{a, i},
a = DeleteCases[
Table[(3 + 10 i), {i, start, start + listlength - 1}], _?PrimeQ];
a = Join[a,
DeleteCases[
Table[(7 + 10 i), {i, start, start + listlength - 1}], _?PrimeQ]];
a = DeleteCases[a, Except[_?(Divisible[Fibonacci[# + 1], #] &)]];
a = DeleteCases[a, Except[_?(Divisible[2^(# - 1) - 1, #] &)]];
Print["Found ", Length[a], " candidates (3 + 10n) or (7 + 10n) between
", TraditionalForm[start], " and ", (start + listLength - 1), "."];
a
];
Monitor[
Do[
Print[
"Iteration: ", ToString[iters + 1], ". Currently testing around: ", ToString[7 + 10*(1 + iters*listLength)], " and a Fibbonaci number with : ", Length[IntegerDigits[Fibonacci[7 + 10*(1 + iters*listLength)]]], " digits: ", nextBlock[1 + iters*listLength, listLength]
],
{iters, startingIter, maxIters}],
ProgressIndicator[iters, {startingIter, maxIters}]
]
The strategy here is that each time nextBlock[] is called, it first creates a list of all composite integers in the desired range which are congruent to $3$ or $7 \mod 10$. Next, it removes any which do not divide the appropriate Fibonacci number, and then removes any that are not Fermat Pseudo-prime. It's fast enough on my system to do 20 iterations in a reasonable amount of time.
Basically I have no clue what to do next to speed this up. I've looked into Compile[]
but the Fibonacci numbers in question have hundreds of thousands of digits, so I can't do that. If anyone is good with parallelization, I could use some guidance since the documentation is difficult to follow. I have an i7 CPU and access to another PC with Mathematica and 4 cores, so if I could figure that out I would probably speed things up a bunch.
I haven't done anything with GPU acceleration in many years, is it possible to port GMP onto CUDA or OpenCL?
FindInstance
. Could you verify that this is equivalent:FindInstance[ (Mod[n, 10] == 3 || Mod[n, 10] == 7) && Mod[Fibonacci[n + 1], n] == 0 && Mod[2^(n - 1) - 1, n] == 0 && Not[Element[n, Primes]] && n > 0, n, Integers, 1]
It will probably sit there for billions of years or forever. Are you sure there is a single number that satisfies these constraints? If you want a faster solution you'll have to use a more intelligent algorithm than brute force. $\endgroup$ – Histograms May 25 '15 at 15:33Fibonacci[2^64 + 1]
givesOverflow[ ]
I'm thinking you might be able to leverage the Fibonacci square test somehow to avoid calculating the Fib altogether, if either (5 (k+1)^2 + 4) or (5 (k+1)^2 - 4) is square, k+1 is a Fibonacci number... tricky $\endgroup$ – Histograms May 25 '15 at 16:24