A306779 Table read by rows: T(n,k) is the length of the longest non-intersecting loop starting at (0,0) on the n X k torus consisting of steps up and to the right, 1 <= k <= n.

1, 2, 4, 3, 5, 9, 4, 8, 11, 16, 5, 9, 14, 19, 25, 6, 12, 18, 24, 29, 36, 7, 13, 19, 27, 33, 41, 49, 8, 16, 23, 32, 38, 48, 55, 64, 9, 17, 27, 35, 44, 54, 62, 71, 81, 10, 20, 29, 40, 50, 60, 69, 80, 89, 100, 11, 21, 32, 43, 53, 65, 76, 87, 97, 109, 121

Offset

1,2

Comments

Conjecture: T(n,k) = n*k if and only if k = 1 or gcd(n,k) > 1.

Proof from Tamás Fülöp, Nov 07 2025: (Start)

T(n, 1) = n*1 trivially.

(=>)

Suppose T(n, k) = n*k, k != 1, and gcd(n, k) = 1,

then 1 <= a <= k, 1 <= b <= n : gcd(a, b) = 1 and a*n+b*k = n*k.

gcd(n, k) = 1 and b*k = n*(k-a) imply k|(k-a), k|(k-a) implies k|a,

k|a and 1 <= a <= k imply a = k, but then b = n*(k-a)/k = 0, contradicting b >= 1.

(<=)

Let d = gcd(n, k) > 1, n = d*u, k = d*v with gcd(u, v) = 1.

Choose 1 <= t <= d-1 using the Chinese remainder theorem

so that t !== d (mod p) for every prime p|v, gcd(t, u) = 1.

Let x = v*t, then n*x/k = u*t implies n*x == 0 (mod k).

k-x = d*v-v*t = v*(d-t), then gcd(k-x, floor(n*x/k)) = gcd(v*(d-t), u*t) = 1.

Using the second formula with the conditions satisfied, we get T(n, k) = n*k. (End)

Links

Tamás Fülöp, Rows n = 1..100 of triangle, flattened

Formula

From Tamás Fülöp, Nov 05 2025: (Start)

T(n, k) = max{a*n+b*k : 1 <= a <= k, 1 <= b <= n, a*n+b*k <= n*k, gcd(a, b) = 1}.

T(n, k) = n*k - min{(n*x) mod k : 0 <= x <= k-1, gcd(k-x, floor(n*x/k)) = 1}. (End)

Example

T(8, 5) = 38 = 1*8+6*5, where d = gcd(1, 6) = 1 and the loop visits (0,0) d+1 times. - Tamás Fülöp, Nov 05 2025
Table begins:
  1;
  2,  4;
  3,  5,  9;
  4,  8, 11, 16;
  5,  9, 14, 19, 25;
  6, 12, 18, 24, 29, 36;

Prog

(Python)
from math import gcd
def T(n, k): return n*k-min((n*x)%k for x in range(k) if gcd(k-x, n*x//k)==1)
print([T(n, k) for n in range(1, 12) for k in range(1, n+1)]) # Tamás Fülöp, Nov 05 2025

Crossrefs

Cf. A324603, A324604.

Sequence in context: A243573 A132193 A185910 * A349947 A351652 A333087

Adjacent sequences: A306776 A306777 A306778 * A306780 A306781 A306782

Keyword

tabl,nonn,easy,walk

Author

Peter Kagey, Mar 09 2019

Extensions

More terms from Tamás Fülöp, Nov 05 2025

Status

approved