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, 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.

Links

Table of n, a(n) for n=0..68.

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

Cf. A048058 (the table of n mod k).

Sequence in context: A303235 A350774 A282062 * A326167 A308590 A309064

Adjacent sequences: A318123 A318124 A318125 * A318127 A318128 A318129

Keyword

nonn

Author

Luc Rousseau, Aug 18 2018

Status

approved