A135317 Let h(2*n, 1) = 2*n and h(2*n, m) = h(2*n, m-1) + 2 * d(2*n, m) for m > 1, where d(2*n, m) = (least multiple of m not less than h(2*n, m-1)) - h(2*n, m-1). Then d(2*n, m) is eventually 2-periodic as a function of m, and a(n) is defined as d(2*n, 2*m+1) for large m.

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

Offset: 0

Author

Alex Abercrombie, Feb 15 2008

Keywords

• nonn

Comments

Sequence yielding an ordering of N*N derived from a family of recurrences.

For any integer k define h(k,1)=k and for m>1 define h(k,m)=h(k,m-1)+2*((-h(k,m-1)) mod m) where "r mod s" denotes least nonnegative residue of r modulo s [informally, h(k,m) is got by "reflecting" h(k,m-1) in the least multiple of m that is >=h(k,m-1)]. Then for fixed k>=0 there are integers c(k), b(k), m(k) such that for all m>m(k) we have h(k,2*m+1)-h(k,2*m)=2*c(k) and h(k,2*m+2)-h(k,2*m+1)=2*b(k). [In the terms of the function d defined in the Name, c(k) = d(k, 2*m+1) and b(k) = d(k, 2*m+2) for all m>m(k).]

For all n we have c(2*n+1)=c(2*n) and b(2*n+1)=1+b(2*n). Moreover b(2*n) is even for all n. The function n->(c(2*n),b(2*n)/2) is a bijection from the nonnegative integers N to N*N [as well as n->(b(n),c(n))]. It is "monotone" in the sense that n<=n' whenever c(2*n)<=c(2*n') and b(2*n)<=b(2*n').

This sequence is a(n) = c(2*n).

The results on which the definition is based are not yet proved, but they are plausible and overwhelmingly supported by numerical evidence.

For each fixed m, k->h(k,m) is a bijection Z->Z (this is easy!). However for k<0 the sequence h(k,m) does not have the pseudo-periodic property we have used in defining c(k) and b(k).

m(k) appears to be O(sqrt k).

From Andrey Zabolotskiy, Dec 28 2024: (Start)

See my Github link for the proof that the sequence is indeed well-defined.

That fact is equivalent to the quantity d(k,m) + d(k,m+1) eventually becoming constant. That constant value can be first reached when m is odd (case B) or even (case C).

On the plane (b(k), c(k)), the points from case B (resp. case C) fall in the region which is approximately the octant b(k) > c(k) (resp. c(k) > b(k)).

On the plane (x=n, y=a(n)), the graph of this sequence fills in a certain region in the plane. It's bounded from below by the line y=0 and from above, it seems, by the curve y = sqrt(Pi*x). That region, it seems, is further divided into two parts: the one below the curve y = sqrt((4/Pi)*x) contains points from case B, the one above it contains points from case C. The latter part looks more dense on the graph. (End)

Examples

			h(18,m) for m>=1 goes 18,18,18,22,28,32,38,42,48...so we can take m(18) = 2, then 2*c(18)=28-22=38-32=48-42=...=6, so a(9) = c(18) = 3 and similarly b(18) = 2.
		

Links

• Andrey Zabolotskiy, Table of n, a(n) for n = 0..20000
• Jon Maiga, Computer-generated formulas for A135317, Sequence Machine.
• Andrey Zabolotskiy, Abercrombie's sequence, Github (formalized Lean proof that this sequence is well-defined).

Crossrefs

Cf. A319571, A319572, A319573, A252448.

Programs

Mathematica

a[n_] := Module[{h = 2 n, b, c = 0, m = 1},
   While[Ceiling[h/(m+1)] != Floor[h/m],
    m++; b = Mod[-h, m]; h += 2 b;
    m++; c = Mod[-h, m]; h += 2 c];
   c];
Table[a[n], {n, 0, 93}] (* Andrey Zabolotskiy, Apr 29 2023, Dec 25 2024 *)

Python

def a(n):
    h, m, c = 2*n, 1, 0
    while (h+m)//(m+1) != h//m:
        m += 1; b = (-h) % m; h += 2*b
        m += 1; c = (-h) % m; h += 2*c
    return c
print([a(n) for n in range(30)]) # Andrey Zabolotskiy, Dec 25 2024

Formula

It appears that a(n) = A319573(A252448(2*n+1)) [discovered by Sequence Machine], moreover, c(n) = A319573(n') and b(n) = A319572(n') with n' = A252448(n), where b and c are described above. - Andrey Zabolotskiy, Apr 28 2023

Extensions

Edited by Andrey Zabolotskiy, Apr 29 2023