login
Euclid's triangle read by rows. T(n, k) = 1 if k is prime to n, otherwise 0.
11

%I #51 May 14 2024 16:59:38

%S 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,

%T 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,

%U 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

%N Euclid's triangle read by rows. T(n, k) = 1 if k is prime to n, otherwise 0.

%C 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.

%C From _Peter Luschny_, Jul 28 2023: (Start)

%C 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.

%C 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)

%D 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.]

%H Paolo Xausa, <a href="/A217831/b217831.txt">Table of n, a(n) for n = 0..11475</a> (rows 0..150 of the triangle, flattened).

%H John C. Turner, <a href="http://jcturner.co.nz/">Musings of a Mathematician</a>

%H John C. Turner and William J. Rogers, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from235to254.pdf">A representation of the natural numbers by means of cycle-numbers, with consequences in number theory</a>, 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 <a href="http://hdl.handle.net/10289/9070">also</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RelativelyPrime.html">Relatively Prime</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Coprime_integers">Coprime integers</a>.

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

%F From _Peter Luschny_, Jul 28 2023: (Start)

%F T(n, 0) = 1 = T(n, n) if n = 1, otherwise 0.

%F T(n, 1) = 1 = T(n, n-1) if n >= 1.

%F For n >= 2 the row sum is A000010(n).

%F Each row is palindromic. (End)

%e The triangle begins:

%e [ 0] [0],

%e [ 1] [1, 1],

%e [ 2] [0, 1, 0],

%e [ 3] [0, 1, 1, 0],

%e [ 4] [0, 1, 0, 1, 0],

%e [ 5] [0, 1, 1, 1, 1, 0],

%e [ 6] [0, 1, 0, 0, 0, 1, 0],

%e [ 7] [0, 1, 1, 1, 1, 1, 1, 0],

%e [ 8] [0, 1, 0, 1, 0, 1, 0, 1, 0],

%e [ 9] [0, 1, 1, 0, 1, 1, 0, 1, 1, 0],

%e [10] [0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0],

%e [11] [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],

%e ...

%e Seen as an array:

%e [ 0] 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e [ 1] 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e [ 2] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...

%e [ 3] 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, ...

%e [ 4] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...

%e [ 5] 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, ...

%e [ 6] 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, ...

%e [ 7] 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, ...

%e [ 8] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...

%e [ 9] 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, ...

%e [10] 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, ...

%e [11] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, ...

%p T := proc(n,k) option remember; local j;

%p if n=0 and k=0 then 0;

%p elif n=1 then 1;

%p elif k=0 or k=n then 0;

%p elif k>n then T(k,n);

%p else j:= (k mod n); T(n-j,j); fi; end;

%p g := n -> [seq(T(n-i,i), i=0..n)];

%p [seq(g(n),n=0..20)]; # _Peter Luschny_, Jul 28 2023

%p # Alternative:

%p A217831 := (n, k) -> if NumberTheory:-AreCoprime(n, k) then 1 else 0 fi:

%p for n from 0 to 11 do seq(A217831(n, k),k=0..n) od; # _Peter Luschny_, May 14 2024

%t 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 *)

%t Table[Boole[CoprimeQ[n,k]],{n,0,10},{k,0,n}] (* _Paolo Xausa_, Nov 24 2023 *)

%o (SageMath)

%o def coprimes(n): return [int(gcd(i, n) == 1) for i in (0..n)]

%o for n in range(12): print(coprimes(n)) # _Peter Luschny_, Jul 28 2023

%o (Python)

%o def Euclid(x, y):

%o while y != 0: t = y; y = x % y; x = t

%o return 1 if x == 1 else 0

%o def EuclidTriangle(L): return [Euclid(i,n) for n in range(L) for i in range(n+1)]

%o print(EuclidTriangle(12)) # _Peter Luschny_, Jul 29 2023

%Y Cf. A000010, A349136, A055034, A062570, A023022, A092790, A056188, A023896, A092790, A053818, A063524 (main diagonal), A113704.

%Y Cf. A054431, A054521, A300294, A367544 - A367547.

%K core,nice,easy,nonn,tabl

%O 0

%A _N. J. A. Sloane_, Oct 14 2012

%E New name by _Peter Luschny_, Jul 28 2023