login
A318126
a(n) is the number of pieces of the simplest continuous piecewise linear function that agrees with n mod k for all positive integer k.
1
1, 2, 3, 4, 5, 4, 5, 6, 7, 7, 7, 6, 7, 8, 9, 10, 10, 9, 10, 11, 11, 12, 11, 10, 11, 12, 13, 13, 14, 13, 13, 14, 15, 15, 14, 13, 14, 15, 16, 16, 17, 16, 16, 17, 17, 18, 17, 16, 16, 17, 19, 19, 18, 17, 17, 20, 19, 18, 17, 16, 17, 18, 19, 20, 21, 19, 20, 21, 22
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.
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
Cf. A048058 (the table of n mod k).
Sequence in context: A303235 A350774 A282062 * A326167 A308590 A309064
KEYWORD
nonn
AUTHOR
Luc Rousseau, Aug 18 2018
STATUS
approved