Will any prime factor of the 1801st Fibonacci Number be found by 2025?
➕
Plus
22
Ṁ1244
Jan 1
19%
chance

Resolves YES if any prime factors have been found for Fibonacci(1801) by the close date.

Resolves NO otherwise.

Current factorization status: http://factordb.com/index.php?query=I%281801%29

F(1801) is notable due to being known to be a composite number, but having no known factors, and for being the next candidate for Fibonacci numbers that are themselves semiprimes (composites with exactly two prime factors), as well as their digit reversal being semiprimes (the digit reverse of F(1801) is a known semiprime). If a single prime factor is found, F(1801) will definitively be either a semiprime or not, due to the ease of checking whether the remaining cofactor is composite or prime.

Being a 377-digit composite number means that using certain factoring techniques like SIQS, SNFS, or GNFS are too burdensome to employ, as the record for the largest GNFS factorization was on a 320-digit composite number that used a combined 325 CPU-years of distributed computation.

This means that the only computationally feasible way that a prime factor could be found for F(1801) is by employing Lenstra elliptic-curve factorization (ECM), a technique that uses elliptic algebraic curves to find "small" prime factors stochastically. The record for size of factor found so far is 83-digits long. Essentially, ECM is like "fishing" for factors, and the beauty of the technique is that if you "run <X> curves at <B1> without finding any factors", it conveys probabilistic knowledge of the characteristics of the prime factors of a composite number. For instance, we know that the following ECM curves have been run on F(1801) by various people:
26658 @ 110M
6500 @ 260M
650 @ 850M
The second number is a parameter used by the ECM algorithm that roughly correlates to the size of the searched for factor.

Since we know these curves have been run without the finding of a factor, we now know certain probabilities of the existence of certain sizes of factors, like so:

This means we can be essentially certain that no prime factors exist of length <50-digits, we expect that we would more likely than not would've found a prime factor of size ~58, and, in the lingo, we would call the amount of "work" done on composite, t58.903

So we are essentially hoping that there exists a prime factor of F(1801) that is between 50 and 83(ish) digits long, and casting out a net to try to find it with computation. Since F(1801) is 377 digits long and composite, we can assume that, at maximum, its factors are at most 188 digits long (in the case that it is semiprime and has two equally "rough" factors of 188-digit length), though that would be a very surprising result. So there exists the possibility that the factor is between 50 and 188 digits in length, though trying to guess the distribution here seems futile. If it is not a semiprime, we know that the maximum factor size could be 125-digits, due to having at least 3 factors.

BUT, there still exists the distinct possibility that the next ECM curve run (by ANYBODY, mind you) finds a prime factor of F(1801), and is currently the most computationally efficient way to work on this problem. You can either download GMP-ECM directly or, use a separate program like YAFU to run ECM curves, like I do, with the following command: yafu-x64.exe -threads 8 -work 58.903 "factor(fib(1801))"

(Feel free to use the comments to ask for technical support in getting started if you want to try to resolve this market YES, or to report how many curves you have run so we will better know when to switch to a higher B1 level)

The current work is t58.903
The current B1 level is 85e7

Get
Ṁ1,000
and
S1.00
Sort by:

I've been trying to motivate myself to get GMP-ECM compiled for GPU on WSL2, so that I can run ECM curves on my new 4090. This specific composite might still be too large to beat my CPU ECM performance, but having this market exist motivates me a bit to get it figured out and see.

predicts NO

okay, after much effort I have a working WSL2 setup with GMP-ECM compiled with GPU and CGBN support, and I have learned much more about the inner workings of the ECM algorithm. for this specific composite number, my GPU is 336x faster at running ECM stage-1 than one thread on my CPU. so if we try to optimize the B1 and B2 parameter sizes such that the GPU finishes stage-1 in the same time it takes 12 threads on the CPU to finish stage-2 we get B1=5.77e8 and B2=3.94e11, with 36335 curves needed to go from t0 to t60. to get to t60 from t58.5 would be 14393 curves, and the GPU stage-1 runs optimally with 8192 curves, so we need 2 runs to get past t60, and each one lasts about 9.5 hours.

so that's running now, and we'll plan how long it takes to get to t65 if we get to t60 with no factors.