A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

1, 1, 2, 1, 2, 3, 1, 3, 3, 4, 1, 2, 3, 4, 5, 1, 4, 5, 5, 5, 6, 1, 2, 3, 4, 5, 6, 7, 1, 5, 3, 7, 5, 7, 7, 8, 1, 2, 7, 4, 5, 8, 7, 8, 9, 1, 6, 3, 7, 9, 8, 7, 9, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 7, 9, 10, 5, 11, 7, 11, 11, 11, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 8, 3, 9, 5, 10, 13, 11, 9, 12, 11, 13, 13, 14

Offset

1,3

Comments

The triangle of fractions A226314(i,j)/A054531(i,j) is an efficient way to enumerate the rationals [Fortnow].

Sum(A226314(n,k)/A054531(n,k): 1<=k<=n) = A226555(n)/A040001(n). - Reinhard Zumkeller, Jun 10 2013

Links

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened

Lance Fortnow, Counting the Rationals Quickly, Computational Complexity Weblog, Monday, March 01, 2004.

Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Example

Triangle begins:
[1]
[1, 2]
[1, 2, 3]
[1, 3, 3, 4]
[1, 2, 3, 4, 5]
[1, 4, 5, 5, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 5, 3, 7, 5, 7, 7, 8]
[1, 2, 7, 4, 5, 8, 7, 8, 9]
[1, 6, 3, 7, 9, 8, 7, 9, 9, 10]
...
The resulting triangle of fractions begins:
1,
1/2, 2,
1/3, 2/3, 3,
1/4, 3/2, 3/4, 4,
1/5, 2/5, 3/5, 4/5, 5,
...

Maple

f:=(i, j) -> j+(i-j)/gcd(i, j);
g:=n->[seq(f(i, n), i=1..n)];
for n from 1 to 20 do lprint(g(n)); od:

Prog

(Haskell)
a226314 n k = n - (n - k) `div` gcd n k
a226314_row n = a226314_tabl !! (n-1)
a226314_tabl = map f $ tail a002262_tabl where
   f us'@(_:us) = map (v -) $ zipWith div vs (map (gcd v) us)
     where (v:vs) = reverse us'
-- Reinhard Zumkeller, Jun 10 2013

Crossrefs

Cf. A002262.

Cf. A037161, A037162, A066657, A066658.

Sequence in context: A368399 A075106 A196935 * A036995 A225597 A116908

Adjacent sequences: A226311 A226312 A226313 * A226315 A226316 A226317

Keyword

nonn,frac,tabl

Author

N. J. A. Sloane, Jun 09 2013

Status

approved