login
A217831
Euclid's triangle read by rows. T(n, k) = 1 if k is prime to n, otherwise 0.
11
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1
OFFSET
0
COMMENTS
Turner defined his triangle T by use of a 'neck-tie' device, and a 'double-cycling' procedure, in order to define his cycle-numbers. See the links below for further details.
From Peter Luschny, Jul 28 2023: (Start)
Two nonnegative integers n, k are relatively prime or coprime if they are not both equal to 0 and there does not exist an integer d > 1 with d | k and d | n. The triangle is the indicator function of this relation, for 0 <= k <= n.
J. C. Turner thinks that a development of the number system that is more basic than the one obtained from Peano's axioms can be based on this triangle, with the basic concepts of the set {0, 1}, the zero number 0, and a cycle generation operation that he describes in his paper. (End)
REFERENCES
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, Reading, 2nd ed. 1994, thirty-fourth printing 2022, p.115. [The authors propose to use the term 'prime' instead of 'coprime' (as in "a is prime to b"), a suggestion followed in the title.]
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of the triangle, flattened).
John C. Turner and William J. Rogers, A representation of the natural numbers by means of cycle-numbers, with consequences in number theory, Annales Mathematicae et Informaticae, 41 (2013) pp. 235-254. Presented to the Fifteenth International Conference on Fibonacci numbers and Their Applications, in Eger, Hungary, on 25 June 2012. See also.
Eric Weisstein's World of Mathematics, Relatively Prime.
Wikipedia, Coprime integers.
FORMULA
Previous name was: Label the entries T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), T(0,2), T(3,0), ... Then T(n,k) = T(k,n), T(0,0) = 0, T(1,0) = 1, and for n > 1, T(n,0) = 0 and T(n,in+j) = T(n-j,j) (i,j >= 0, not both 0).
From Peter Luschny, Jul 28 2023: (Start)
T(n, 0) = 1 = T(n, n) if n = 1, otherwise 0.
T(n, 1) = 1 = T(n, n-1) if n >= 1.
For n >= 2 the row sum is A000010(n).
Each row is palindromic. (End)
EXAMPLE
The triangle begins:
[ 0] [0],
[ 1] [1, 1],
[ 2] [0, 1, 0],
[ 3] [0, 1, 1, 0],
[ 4] [0, 1, 0, 1, 0],
[ 5] [0, 1, 1, 1, 1, 0],
[ 6] [0, 1, 0, 0, 0, 1, 0],
[ 7] [0, 1, 1, 1, 1, 1, 1, 0],
[ 8] [0, 1, 0, 1, 0, 1, 0, 1, 0],
[ 9] [0, 1, 1, 0, 1, 1, 0, 1, 1, 0],
[10] [0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0],
[11] [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
...
Seen as an array:
[ 0] 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
[ 1] 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
[ 2] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
[ 3] 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, ...
[ 4] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
[ 5] 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, ...
[ 6] 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, ...
[ 7] 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, ...
[ 8] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
[ 9] 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, ...
[10] 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, ...
[11] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, ...
MAPLE
T := proc(n, k) option remember; local j;
if n=0 and k=0 then 0;
elif n=1 then 1;
elif k=0 or k=n then 0;
elif k>n then T(k, n);
else j:= (k mod n); T(n-j, j); fi; end;
g := n -> [seq(T(n-i, i), i=0..n)];
[seq(g(n), n=0..20)]; # Peter Luschny, Jul 28 2023
# Alternative:
A217831 := (n, k) -> if NumberTheory:-AreCoprime(n, k) then 1 else 0 fi:
for n from 0 to 11 do seq(A217831(n, k), k=0..n) od; # Peter Luschny, May 14 2024
MATHEMATICA
T[n_, k_] := T[n, k] = Module[{i, j}, Which[n == 0 && k == 0, 0, n == 1, 1, k == 0 || k == n, 0, k>n, T[k, n], True, j = Mod[k, n]; i = (k-j)/n; T[n-j, j]]]; g[n_] := Table[T[n-i, i], {i, 0, n}]; Table[g[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Mar 06 2014, after Maple *)
Table[Boole[CoprimeQ[n, k]], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Nov 24 2023 *)
PROG
(SageMath)
def coprimes(n): return [int(gcd(i, n) == 1) for i in (0..n)]
for n in range(12): print(coprimes(n)) # Peter Luschny, Jul 28 2023
(Python)
def Euclid(x, y):
while y != 0: t = y; y = x % y; x = t
return 1 if x == 1 else 0
def EuclidTriangle(L): return [Euclid(i, n) for n in range(L) for i in range(n+1)]
print(EuclidTriangle(12)) # Peter Luschny, Jul 29 2023
KEYWORD
core,nice,easy,nonn,tabl
AUTHOR
N. J. A. Sloane, Oct 14 2012
EXTENSIONS
New name by Peter Luschny, Jul 28 2023
STATUS
approved