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

Author

Luc Rousseau, Aug 18 2018

Keywords

• nonn

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.

Examples

			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.
		

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

Crossrefs

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

Programs

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]

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), ", "))