cp's OEIS Frontend

A019587 The left budding sequence: number of i such that 0 < i <= n and 0 < {phi*i} <= {phi*n}, where {} denotes the fractional part and phi = A001622.

%I A019587 #43 Aug 11 2025 01:22:26
%S A019587 1,1,3,2,1,5,3,8,5,2,9,5,1,10,5,15,9,3,15,8,21,13,5,20,11,2,19,9,27,
%T A019587 16,5,25,13,1,23,10,33,19,5,30,15,41,25,9,37,20,3,33,15,46,27,8,41,21,
%U A019587 55,34,13,49,27,5,43,20,59,35,11,52,27,2,45,19,63,36,9,55,27,74,45,16,65
%N A019587 The left budding sequence: number of i such that 0 < i <= n and 0 < {phi*i} <= {phi*n}, where {} denotes the fractional part and phi = A001622.
%D A019587 J. H. Conway, personal communication.
%H A019587 Reinhard Zumkeller, <a href="/A019587/b019587.txt">Table of n, a(n) for n = 1..1000</a>
%H A019587 Hamoon Mousavi et al., <a href="https://walnut-theorem-prover.github.io/">Walnut</a>, An automatic theorem prover for words, <a href="https://github.com/Walnut-Theorem-Prover/Walnut">version 7.0</a>.
%H A019587 N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>
%F A019587 a(n) + A194733(n) = n.
%F A019587 The theorem prover Walnut (see link) can compute the following "linear representation" for a(n). Let v = [1,0,0,0,0,0,0,0,0,0,0,0], w = [0,1,1,3,2,1,5,3,8,5,2,9]^T, mu(0) =[[1,0,0,0,0,0,0,0,0,0,0,0], [0,0,1,0,0,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,0,0,0,0,0], [0,0,0,0,0,1,0,0,0,0,0,0], [0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,0,0,0,1,0,0,0], [0,0,0,0,0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,-1,0,0,2,0], [0,0,-2,0,0,1,0,2,0,0,0,0], [0,0,-1,-1,0,1,0,1,1,0,-1,1], [0,0,-1,0,0,0,0,0,0,0,2,0]], mu(1) = [[0,1,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,1,0,0,0,0,0,0,0], [0,0,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,-1,0,0,2,0,0], [0,-2,0,0,1,0,2,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0], [0,-1,0,0,0,0,0,0,0,2,0,0], [0,-4,0,0,2,0,4,0,0,-1,0,0]]. Then a(n) = v.mu(x).w, where x is the Zeckendorf (or Fibonacci) representation of n. This gives an algorithm for a(n) that runs in polynomial time in log n. - _Jeffrey Shallit_, Aug 09 2025
%e A019587 {r} = 0.61...; {2r} = 0.23...; {3r} = 0.85...; {4r} = 0.47...; so that a(4) = 2.
%p A019587 Digits := 100;
%p A019587 A019587 := proc(n::posint)
%p A019587     local a,k,phi,kfrac,nfrac ;
%p A019587     phi := (1+sqrt(5))/2 ;
%p A019587     a :=0 ;
%p A019587     nfrac := n*phi-floor(n*phi) ;
%p A019587     for k from 1 to n do
%p A019587         kfrac := k*phi-floor(k*phi) ;
%p A019587         if evalf(kfrac-nfrac)  <= 0 then
%p A019587             a := a+1 ;
%p A019587         end if;
%p A019587     end do:
%p A019587     a ;
%p A019587 end proc:
%p A019587 seq(A019587(n),n=1..100) ; # _R. J. Mathar_, Aug 13 2021
%t A019587 r = GoldenRatio; p[x_] := FractionalPart[x];
%t A019587 u[n_, k_] := If[p[k*r] <= p[n*r], 1, 0]
%t A019587 v[n_, k_] := If[p[k*r] > p[n*r], 1, 0]
%t A019587 s[n_] := Sum[u[n, k], {k, 1, n}]
%t A019587 t[n_] := Sum[v[n, k], {k, 1, n}]
%t A019587 Table[s[n], {n, 1, 100}]  (* A019587 *)
%t A019587 Table[t[n], {n, 1, 100}]  (* A194733 *)
%t A019587 (* _Clark Kimberling_, Sep 02 2011 *)
%o A019587 (Haskell)
%o A019587 a019587 n = length $ filter (<= nTau) $
%o A019587             map (snd . properFraction . (* tau) . fromInteger) [1..n]
%o A019587    where (_, nTau) = properFraction (tau * fromInteger n)
%o A019587          tau = (1 + sqrt 5) / 2
%o A019587 -- _Reinhard Zumkeller_, Jan 28 2012
%Y A019587 Cf. A001622, A019588, A194733, A193738.
%K A019587 nonn,easy,nice
%O A019587 1,3
%A A019587 _N. J. A. Sloane_ and _J. H. Conway_
%E A019587 Extended by _Ray Chandler_, Apr 18 2009