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)).

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

Author

Darío Clavijo, Jun 12 2024

Keywords

• nonn

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).

Examples

			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
		

Links

• Mathematics Stack Exchange, Pollard-Strassen algorithm.
• Programming Praxis, Strassen's factoring algorithm.

Crossrefs

Cf. A002808, A255270.

Programs

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

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(1A373652_list = list(islice(A373652_gen(),20)) # Chai Wah Wu, Jul 16 2024