cp's OEIS Frontend

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.

%I A318126 #25 Nov 11 2019 00:53:07
%S A318126 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,
%T A318126 14,13,13,14,15,15,14,13,14,15,16,16,17,16,16,17,17,18,17,16,16,17,19,
%U A318126 19,18,17,17,20,19,18,17,16,17,18,19,20,21,19,20,21,22
%N 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.
%C A318126 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.
%C A318126 It appears that a(n) is asymptotically sqrt(8n) and that a(n) <= sqrt(8n) for all n >= 1.
%H A318126 Luc Rousseau, <a href="/A318126/a318126.svg">Diagram illustrating a(11)=6 and a(24)=11.</a>
%H A318126 Luc Rousseau, <a href="/A318126/a318126.png">Plot of a(n) and sqrt(8*n) for n in 0..163</a>
%H A318126 Wikipedia, <a href="https://en.wikipedia.org/wiki/Piecewise_linear_function">Piecewise linear function</a>
%e A318126 With n=5, the list of values of (n mod k), i.e., {0, 1, 2, 1, 0, 5, 5, 5, ...} is modeled by:
%e A318126 - {0, 1, 2} = k - 1 between k=1 and k=3,
%e A318126 - {2, 1, 0} = 5 - k between k=3 and k=5,
%e A318126 - {0, 5} = 5*k - 25 between k=5 and k=6,
%e A318126 - {5, 5, 5, ...} = 5 between k=6 and positive infinity.
%e A318126 Four intervals are involved, so a(5) = 4.
%t A318126 a[n_] := Module[{d = Differences[(Mod[n, #] &) /@ Range[n + 2]],
%t A318126    r = 1, k},
%t A318126   For[k = 2, k <= Length[d], k++, If[d[[k]] != d[[k - 1]], r++]];
%t A318126   r]; a /@ Range[0, 68]
%o A318126 (PARI)
%o A318126 nxt(n,x)=my(y=floor(n/floor(n/x)));if(y==x,x+1,y)
%o A318126 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
%o A318126 for(n=0,68,print1(a(n), ", "))
%Y A318126 Cf. A048058 (the table of n mod k).
%K A318126 nonn
%O A318126 0,2
%A A318126 _Luc Rousseau_, Aug 18 2018