cp's OEIS Frontend

A286389 a(0) = 0; a(n) = n - a(floor(a(n-1)/2)).

%I A286389 #57 Sep 02 2025 23:30:41
%S A286389 0,1,2,2,3,4,4,5,6,7,8,8,9,10,10,11,12,13,14,14,15,16,16,17,18,18,19,
%T A286389 20,20,21,22,23,24,24,25,26,26,27,28,29,30,30,31,32,32,33,34,34,35,36,
%U A286389 36,37,38,39,40,40,41,42,42,43,44,45,46,46,47,48,48,49,50,51,52,52,53,54,54,55,56,57,58,58
%N A286389 a(0) = 0; a(n) = n - a(floor(a(n-1)/2)).
%C A286389 A variation on Hofstadter's G-sequence.
%C A286389 Conjecture: partial sums of A285431 (verified for n <= 400). - _Sean A. Irvine_, Jul 20 2022
%C A286389 The conjecture has been verified for n <= 50000. - _Michel Dekking_, Jul 06 2023
%C A286389 Irvine's conjecture is now proven using the Walnut theorem prover. - _Jeffrey Shallit_, Oct 21 2023
%H A286389 Anton Mosunov, <a href="/A286389/b286389.txt">Table of n, a(n) for n = 0..400</a>
%H A286389 Jeffrey Shallit, <a href="https://arxiv.org/abs/2310.14252">Proof of Irvine's conjecture via mechanized guessing</a>, arXiv preprint arXiv:2310.14252 [math.CO], October 22 2023.
%H A286389 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%F A286389 Conjecture: a(n) ~ c*n, where c = sqrt(3) - 1 = 0.732050807...
%F A286389 From _Michel Dekking_, Jul 06 2023: (Start)
%F A286389 This conjecture is implied by the conjecture in the COMMENTS, by a simple application of the Perron-Frobenius Theorem.
%F A286389 The vector (1, 1 + sqrt(3)) is a right eigenvector of the incidence matrix of the morphism 0->11, 1->110. Therefore the frequency of 1 in A285431 is equal to sqrt(3) - 1. So if the conjecture in the COMMENTS is true, then this implies that a(n)/n converges to sqrt(3) - 1. (End)
%t A286389 a[0] = 0; a[n_] := a[n] = n - a[Floor[a[n - 1]/2]]; Array[a, 80, 0]
%o A286389 (PARI) a(n)=if(n>0,return(n-a(floor(a(n-1)/2))));return(0); \\ _Anton Mosunov_, May 26 2017
%Y A286389 Cf. A005206, A138466, A160390.
%K A286389 nonn,changed
%O A286389 0,3
%A A286389 _Ilya Gutkovskiy_, May 24 2017