login
Number of nonempty sets {p_1, p_2, ..., p_k} such that Product_{i=1..k} p_i divides Product_{i=1..k} (n + p_i), where the p_i are distinct primes.
0

%I #14 May 24 2020 03:00:36

%S 1,3,4,7,6,19,8,17,8,25,12,105

%N Number of nonempty sets {p_1, p_2, ..., p_k} such that Product_{i=1..k} p_i divides Product_{i=1..k} (n + p_i), where the p_i are distinct primes.

%C a(n) always exists. Proof: let p_1 < p_2 < ... < p_k, we can prove p_k <= 2*n^2 + n. If p_k > 2*n^2 + n, then 2*p_k > p_i + n, thus p_k - n is in the set. If p_k - m*n is in the set and m < n, then 2*(p_k - m*n) > p_i + n, thus p_k - (m+1)*n is in the set. Therefore, p_k - m*n are in the set for 0 <= m <= n. Since p_k - n*n > n + 1, p_k - m*n can be divisible by n + 1 for some m <= n, which is a contradiction to the p_i being primes.

%e For n = 3, {3}, {2, 3}, {2, 5} and {2, 3, 5} are such sets, thus a(3) = 4.

%o (PARI) a(n, k=primepi(2*n^2+n)) = {my(c=-1, p=primes(k)); forsubset(k, v, if(vecprod(vector(#v, i, p[v[i]]+n))%vecprod(vector(#v, i, p[v[i]])) == 0, c++)); c; }

%K nonn,more

%O 1,2

%A _Jinyuan Wang_, May 10 2020