OFFSET
1,2
COMMENTS
The P_(n+2)-rough numbers less than the (n+1)-th primorial also comprise the reduced residue system of the (n+1)-th primorial.
The conjectured formula from Jon E. Schoenfield is true. This can be seen by considering that each odd prime p has exactly (p+1)/2 quadratic residues (mod p), of which (p-1)/2 are nonzero. The P_(n+2)-rough numbers less than the (n+1)-th primorial comprise all combinations of nonzero residues modulo the first n+1 primes. So for each odd prime p, the p-1 nonzero residues map to (p-1)/2 (nonzero) residues after squaring. - Bert Dobbelaere, Aug 09 2023
LINKS
Eric Weisstein's World of Mathematics, Primorial
Eric Weisstein's World of Mathematics, Rough Number
FORMULA
Conjecture: a(n) = (1/2^n)*Product_{j=1..n} (prime(j+1)-1) = A005867(n+1)/2^n. - Jon E. Schoenfield, Feb 20 2019
a(n) = A323739(n+1). - Bert Dobbelaere, Aug 09 2023
EXAMPLE
For n=2, P_(n+2) = 7.
The 7-rough numbers less than 2*3*5 are 1,7,11,13,17,19,23,29.
The squares of those numbers mod 2*3*5 are 1,19,1,19,19,1,19,1.
There are 2 different results: 1 and 19; so a(2) = 2.
PROG
(Java)
import java.util.TreeSet;
for(int z = 1; z < 10 ; z++) {
int n = z;
int numNumPerLine = 210;
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43};
int numRepeats = 1;
int numSpaces = 1;
for(int i = 0; i < n + 1; i++) {
numSpaces *= (primes[i] - 1);
}
int counter = 0;
long integerLength = 1;
for(int i = 0; i < n + 1; i++) {
integerLength *= primes[i];
}
TreeSet<Long> numResults = new TreeSet<Long>();
numSpaces/=2;
for(int i = 1; i < integerLength / 2; i+=2) {
boolean isInList = true;
for(int j = 1; j < n + 1; j++) {
if(i % primes[j] == 0) {
isInList = false;
}
}
if(isInList) {
long k = i % integerLength;
if(k != 0) {
long l = (k * k) % integerLength;
if(!numResults.contains(l)) {
numResults.add(l);
}
}
}
}
System.out.println(numResults.size());
}
(PARI) a(n) = {hp = prod(k=1, n+1, prime(k)); rp = prod(k=1, n+2, prime(k)); v = []; for (i=1, hp, if (gcd(i, rp) == 1, nv = i^2 % hp; if (! vecsearch(v, nv), v = vecsort(concat(v, nv))); ); ); #v; } \\ Michel Marcus, Sep 06 2014
CROSSREFS
KEYWORD
nonn
AUTHOR
John B. Yin, Aug 29 2014
STATUS
approved