|
| |
|
|
A217831
|
|
Euclid's triangle read by rows. T(n, k) = 1 if k is prime to n, otherwise 0.
|
|
6
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
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
|
|
|
|
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).
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)];
# Alternative:
Ib := b -> round(evalhf(b)): # Iverson bracket
A217831row := n -> local k: seq(Ib(igcd(k, n) = 1), k = 0..n):
|
|
|
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)]
|
|
|
CROSSREFS
|
Cf. A000010, A349136, A055034, A062570, A023022, A092790, A056188, A023896, A092790, A053818, A063524 (main diagonal), A113704.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
