A319148 Irregular triangle T(n,m) where row n lists differences m = j*p - r - 1, with iterator 1 <= j <= A002110(n), p = prime(n+1), and r is the smallest number that exceeds j*p that is coprime to A002110(n+1).

0, 1, 0, 1, 0, 1, 2, 3, 0, 3, 2, 1, 0, 1, 0, 3, 2, 3, 0, 1, 4, 5, 2, 1, 0, 1, 0, 3, 2, 1, 2, 1, 0, 3, 4, 1, 0, 5, 0, 1, 0, 3, 2, 3, 0, 1, 0, 1, 2, 5, 4, 5, 2, 1, 2, 3, 0, 1, 0, 1, 4, 3, 4, 1, 2, 1, 2, 3, 0, 5, 0, 3, 2, 3, 0, 1, 0, 1, 2, 5, 0, 5, 2, 3, 2, 3, 0, 1, 0, 1, 4, 3, 4, 1, 0, 1

Offset: 1

Author

Jamie Morken, Sep 11 2018

Keywords

• nonn
• tabf

Comments

Let p(i) be primes with p(1)=2, p(n)# the n-th primorial number, and h(n) the Jacobsthal function for primorial p(n)#. Conjecture: gcd(h(n), p(n+1)) = 1.

For a multiple m of a prime n, terms in this sequence give the number of contiguous numbers starting at m+1 which have at least one prime factor < n.

Consider a range s of the first n + 1 primes. Let p be the largest of these primes, i.e., A000040(n+1). Let P be the product of the first n primes, i.e., the primorial A002110(n), and let Q be the product of all the primes in s, i.e., the primorial A002110(n+1). Consider the reduced residue system R of primorial P, that is, those numbers 1 <= r < P such that gcd(r, P) = 1; therefore R = row n of A286941. For each n, we generate the multiples k = j*p, with 1 <= j <= P. For each k, we find the smallest residue r in R that exceeds k and take the difference m = r - k - 1. If no value in R exceeds k, then we use Q + 1 (which is also coprime to Q). Row n is thus a list of these m.

Alternatively, consider a multiple k = j*p, with 1 <= j <= P. We can compute m by iterating i such that the sum (i + k) is coprime to Q and subtracting 1. This technique is more efficient in terms of memory, as it does not require storing the reduced residue system of Q.

For n > 1: The penultimate value m on row n = A040976(n). The number of values m on row n is given by the sequence: 1,1,2,2,10,22,500,...

For n > 3: For any even x = m in row n, the number of x in row n is equal to the count of y in row n where y = x + 1. If x = 0, the count of x and y in row n = A000010(A002110(n-1)). For example, on row 4, A000010(A002110(4-1)) = 8, as 0 and 1 each occur 8 times on row 4. The sequence of counts of x and x+1 pairs on consecutive rows is given by the sequence A059861. For example, for x=0 and y=1 occurring 8 times on row 4, x=2 and y=3 occur 8-3=5 times on row 4 given by the value 3 in A059861. For example, for row 8, x=0 and y=1 occur A000010(A002110(8-1)) = 92160 times on row 8, and x=2 and y=3 occur 92160-22275=69885 times on row 8 given by the value 22275 in A059861.

For 3 < n < 9: The largest value on row n occurs twice, the pattern of occurrence is shown in table 1 of Ziller & Morack in the Links section.

Examples

			Triangle begins:
  0;
  1,0;
  1,0,1,2,3,0;
  3,2,1,0,1,0,3,2,3,0,1,4,5,2,1,0,1,0,3,2,1,2,1,0,3,4,1,0,5,0;
  ...
For n = 2, we have s = {2,3,5}, with p = prime(n+1) = 5, P = A002110(2) = 6, and Q = A002110(3) = 30. Then R = row n of A286941 = {1, 7, 11, 13, 17, 19, 23, 29} (we add 31 to this list since we are concerned with the residue that is larger than the largest k and since 31 is the ensuing number coprime to Q). The series of multiples k = j*p are the multiples 5j with 1 <= j <= P, thus {5, 10, 15, 20, 25, 30}. In R, the smallest residues that exceed the multiples k in the immediately aforementioned list are {7, 11, 17, 23, 29, 31}. The differences are {7 - 5, 11 - 10, 17 - 15, 23 - 20, 29 - 25, 31 - 30} or {2, 1, 2, 3, 4, 1}; subtracting one from each we have row 2 = {1, 0, 1, 2, 3, 0}.
For example, the third value on row n=20000 is 15, so all values in the range (3 * prime(20000) + i) to (3 * prime(20000) + i) for 1 <= i <= 15 have at least one prime factor <= prime(n).
		

Links

• Mario Ziller and John F. Morack, Algorithmic concepts for the computation of Jacobsthal's function, arXiv:1611.03310 [math.NT], 2016.
• Mario Ziller, New computational results on a conjecture of Jacobsthal, arXiv:1903.11973 [math.NT], 2019.

Crossrefs

Cf. A000040, A002110, A005867, A040976, A046933, A048670, A059861, A286941.

Programs

Mathematica

rowToCreate = 3; (* create row n *)
redundantDistanceToCheck = 1; (* set to 2 or higher to see n repeating
patterns of length primorial[rowToCreate] *)
Primorial[n_] := Times @@ Prime[Range[n]]
rowValue = 0;
primeToUse = Prime[rowToCreate];
distanceToCheck1 = redundantDistanceToCheck*Primorial[rowToCreate];
(* distanceToCheck1=rowToCreate*10000; *)(* uncomment this second option to create the first few values in very large rows up to rowToCreate=7000000000000 *)
For[i = primeToUse, i < distanceToCheck1 + 1, i = i + primeToUse,
For[x = i + 1, x < distanceToCheck1 + 2, x++,
If[FactorInteger[x][[1, 1]] < primeToUse, rowValue++; , x =
distanceToCheck1 + 2;
Print[rowValue];
rowValue = 0;
]]] (* Jamie Morken, Sep 11 2018 *)
(* Program to check the number of composites referenced to row
values: *)
Row = 100;
ColumnOnTheRow = 12;
Print["composites>", ColumnOnTheRow*Prime[Row], "=",
(NextPrime[ColumnOnTheRow*Prime[Row]]) -
(ColumnOnTheRow*Prime[Row]) - 1];
(* Second program: *)
Table[Block[{s = Prime@ Range[n + 1], p, P, Q}, p = Last@ s; P = Times @@
Most@ s; Q = Times @@ s; Array[Block[{k = 1}, While[! CoprimeQ[k + p #,
Q], k++]; k - 1] &, P]], {n, 4}] // Flatten (* Michael De Vlieger, Sep 11 2018 *)

Formula

Length of row n = A002110(n - 1).

T(n,1) = A046933(n).

Number of unique or primitive values m in row n = A048670(n-1).