public class Lehman_AnalyzeCongruences2
extends Object
Analyze a-values that help the Lehman algorithm to find factors, modulo powers of 2.
If we analyze the data in terms of (a0, adjust) pairs, we notice that we always get antidiagonals, each of
them representing a "successful a", because a == (a0 + adjust) (mod m), with m=2^n. So all we need to investigate is "a" (mod m).
Version 2 doubles m step-by-step and analyzes or allows to analyze incremental changes.
Only odd k are analyzed, because the result for even k is trivial (we need all odd "a"-values).
The number of successful a from original k+N congruences are 1, 2, 6, 16, 64, 256, 1024, ...
The last incremental improvement occurs at m=16. This is trivial.
For the more interesting k*N congruences I found experimentally:
The number of successful a are a(n) = 1, 2, 6, 16, 56, 192, 736, 2816, 11136, 44032, ... (not found in OEIS)
dropped a are d(n) = 0, 2, 2, 8, 8, 32, 32, 128, 128, 512, ... (quite trivial)
From that data I derived the iterative formula
a(1) = 1
if (m > 1) {
n = ld(m);
rightExp = 2*floor(n/2) - 1
a(n) = a(n-1)*4 - 2^rightExp
}
having first values
n= 1, m= 2: a(n) = 2^0 = 1
n= 2, m= 4: a(n) = (2^0)*4 - 2^1 = 2^2 - 2^1 = 2
n= 3, m= 8: a(n) = (2^2 - 2^1)*4 - 2^1 = 2^4 - 2^3 - 2^1 = 6
n= 4, m= 16: a(n) = (2^4 - 2^3 - 2^1)*4 - 2^3 = 2^6 - 2^5 - 2^4 = 16
n= 5, m= 32: a(n) = (2^6 - 2^5 - 2^4)*4 - 2^3 = 2^8 - 2^7 - 2^6 - 2^3 = 56
n= 6, m= 64: a(n) = (2^8 - 2^7 - 2^6 - 2^3)*4 - 2^5 = 2^10 - 2^9 - 2^8 - 2^6 = 192
n= 7, m= 128: a(n) = (2^10 - 2^9 - 2^8 - 2^6)*4 - 2^5 = 2^12 - 2^11 - 2^10 - 2^8 - 2^5 = 736
n= 8, m= 256: a(n) = (2^12 - 2^11 - 2^10 - 2^8 - 2^5)*4 - 2^7 = 2^14 - 2^13 - 2^12 - 2^10 - 2^8 = 2816
n= 9, m= 512: a(n) = (2^14 - 2^13 - 2^12 - 2^10 - 2^8)*4 - 2^7 = 2^16 - 2^15 - 2^14 - 2^12 - 2^10 - 2^7 = 11136
n=10, m=1024: a(n) = (2^16 - 2^15 - 2^14 - 2^12 - 2^10 - 2^7)*4 - 2^9 = 2^18 - 2^17 - 2^16 - 2^14 - 2^12 - 2^10 = 44032
...
Computing more values from the iterative formula gives the sequence (starting at n=1)
a(n) = 1, 2, 6, 16, 56, 192, 736, 2816, 11136, 44032, 175616, 700416, 2799616, 11190272, 44752896, 178978816, 715882496, 2863398912, 11453464576, 45813334016, 183252811776, 733009149952, 2932034502656, 11728129622016, 46912510099456, 187650006843392, 750599993819136, 3002399841058816, 12009599230017536, 48038396383199232, ...
Closed formulas I found later on:
a(n) = 2^(n-2) * A023105(n), for n>0
a(2n+2) = 2*A083086(2n), for n>=0
- Author:
- Tilman Neumann