OFFSET
0,2
COMMENTS
For a fixed n, the list of values (n mod k) can be modeled by a continuous piecewise linear function. Its simplest form consists of choosing the least possible number of intervals with integer endpoints. By definition a(n) is this number of intervals.
It appears that a(n) is asymptotically sqrt(8n) and that a(n) <= sqrt(8n) for all n >= 1.
LINKS
Luc Rousseau, Diagram illustrating a(11)=6 and a(24)=11.
Luc Rousseau, Plot of a(n) and sqrt(8*n) for n in 0..163
Wikipedia, Piecewise linear function
EXAMPLE
With n=5, the list of values of (n mod k), i.e., {0, 1, 2, 1, 0, 5, 5, 5, ...} is modeled by:
- {0, 1, 2} = k - 1 between k=1 and k=3,
- {2, 1, 0} = 5 - k between k=3 and k=5,
- {0, 5} = 5*k - 25 between k=5 and k=6,
- {5, 5, 5, ...} = 5 between k=6 and positive infinity.
Four intervals are involved, so a(5) = 4.
MATHEMATICA
a[n_] := Module[{d = Differences[(Mod[n, #] &) /@ Range[n + 2]],
r = 1, k},
For[k = 2, k <= Length[d], k++, If[d[[k]] != d[[k - 1]], r++]];
r]; a /@ Range[0, 68]
PROG
(PARI)
nxt(n, x)=my(y=floor(n/floor(n/x))); if(y==x, x+1, y)
a(n)=my(r=1, x=1, t=n, s=-1, xx, tt, ss); while(t, xx=nxt(n, x); tt=floor(n/xx); ss=(t*x-tt*xx)/(xx-x); if(ss!=s, r++); x=xx; t=tt; s=ss); r
for(n=0, 68, print1(a(n), ", "))
CROSSREFS
KEYWORD
nonn
AUTHOR
Luc Rousseau, Aug 18 2018
STATUS
approved