login
A373652
Composite numbers k for which g = gcd(f(i*c), k) = 1 or k for all i in the range 1 <= i <= c, where f(x) = Product_{j=1..c} x+j and c = floor(k^(1/4)).
0
9, 15, 49, 77, 169, 221, 247, 323, 529, 961, 1147, 1271, 1517, 1680, 1849, 2021, 2209, 2279, 2520, 2688, 2880, 3360, 3481, 3599, 3721, 3953, 4032, 4087, 4320, 4480, 4536, 4757, 5040, 5184, 5329, 5670, 5760, 5767, 6048, 6059, 6241, 6480, 6497, 6557, 6720, 7200
OFFSET
1,1
COMMENTS
These conditions for k are inspired by the Pollard-Strassen factorization algorithm.
f(i*c) is the product of successive blocks of consecutive integers c*i+1 to c*(i+1) inclusive and can be calculated efficiently mod k by a multi-point polynomial evaluation.
The conditions here are that no g by itself reveals a factor of k (so that the Pollard-Strassen algorithm must examine individual c*i+j terms in some g = k block to find a factor).
LINKS
EXAMPLE
For k = 49:
i | c | c*i+1 | c*(i+1) | g
-------------------------------------
1 | 2 | 3 | 4 | 1
2 | 2 | 5 | 6 | 1
Result: 1
For k = 323:
i | c | c*i+1 | c*(i+1) | g
-------------------------------------
1 | 4 | 5 | 8 | 1
2 | 4 | 9 | 12 | 1
3 | 4 | 13 | 16 | 1
4 | 4 | 17 | 20 | 323
Result: 323
PROG
(Python)
from sympy import integer_nthroot, gcd, isprime
def s(k):
c = integer_nthroot(k, 4)[0]
f = [1]*c
for i in range(1, c+1):
for j in range(c*i+1, c*(i+1)+1):
f[i-1] = (f[i-1] * j) % k
f[i-1] = gcd(f[i-1], k)
return f
isok = lambda k: not isprime(k) and not any(k > x > 1 for x in s(k))
print([k for k in range(4, 7200) if isok(k)])
(Python)
from itertools import count, islice
from math import gcd, prod
from sympy import isprime
def A373652_gen(): # generator of terms
for c in count(1):
g = [prod(i*c+j for j in range(1, c+1)) for i in range(1, c+1)]
yield from filter(lambda k: not (k==1 or isprime(k) or any(1<gcd(d, k)<k for d in g)), range(c**4, (c+1)**4))
A373652_list = list(islice(A373652_gen(), 20)) # Chai Wah Wu, Jul 16 2024
(PARI) s(n) = my(c=sqrtnint(n, 4), vf = vector(c, k, 1)); for (i=1, #vf, vf[i] = prod(j=c*i+1, c*(i+1), j % n); vf[i] = gcd(vf[i], n); ); vf;
isok(n) = if ((n>1) && !isprime(n), my(x=Set(s(n)), y=Set([1, n])); setunion(x, y) == y); \\ Michel Marcus, Jun 18 2024
CROSSREFS
Sequence in context: A020272 A020317 A283676 * A305219 A039314 A146584
KEYWORD
nonn
AUTHOR
Darío Clavijo, Jun 12 2024
STATUS
approved