|
%I #49 Jan 15 2024 12:02:43
%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)];
%p # Alternative:
%p Ib := b -> round(evalhf(b)): # Iverson bracket
%p A217831row := n -> local k: seq(Ib(igcd(k, n) = 1), k = 0..n):
%p seq(A217831row(n), n = 0..11); # _Peter Luschny_, Jul 28 2023
%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
|
