cp's OEIS Frontend

A188163 Smallest m such that A004001(m) = n.

%I A188163 #57 Feb 16 2025 08:33:14
%S A188163 1,3,5,6,9,10,11,13,17,18,19,20,22,23,25,28,33,34,35,36,37,39,40,41,
%T A188163 43,44,46,49,50,52,55,59,65,66,67,68,69,70,72,73,74,75,77,78,79,81,82,
%U A188163 84,87,88,89,91,92,94,97,98,100,103,107,108,110,113,117,122
%N A188163 Smallest m such that A004001(m) = n.
%C A188163 How is this related to A088359? - _R. J. Mathar_, Jan 09 2013
%C A188163 It is not hard to show that a(n) exists for all n, and in particular a(n) < 2^n. - _Charles R Greathouse IV_, Jan 13 2013
%C A188163 From _Antti Karttunen_, Jan 10 & 18 2016: (Start)
%C A188163 Positions of records in A004001. After 1 the positions where A004001 increases (by necessity by one).
%C A188163 An answer to the question of _R. J. Mathar_ above: This sequence is equal to A088359 with prepended 1. This follows because at each of its unique values (terms of A088359), A004001 must grow, but it can grow nowhere else. See Kubo and Vakil paper and especially the illustrations of Q and R-trees on pages 229-230 (pages 5 & 6 in PDF) and also in sequence A265332.
%C A188163 Obviously A004001 can obtain unique values only at points which form a subset (A266399) of this sequence.
%C A188163 (End)
%H A188163 Reinhard Zumkeller, <a href="/A188163/b188163.txt">Table of n, a(n) for n = 1..10000</a>
%H A188163 T. Kubo and R. Vakil, <a href="http://dx.doi.org/10.1016/0012-365X(94)00303-Z">On Conway's recursive sequence</a>, Discr. Math. 152 (1996), 225-252.
%H A188163 User "Panurge", <a href="https://mathoverflow.net/questions/234759/frankls-conjecture-and-oeis-sequence-a188163">Frankl's conjecture and Oeis sequence A188163</a>, Mathoverflow.net, Mar 29 2016.
%H A188163 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html">Hofstadter-Conway $10,000 Sequence.</a>
%H A188163 Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>
%H A188163 <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%F A188163 Other identities. For all n >= 1:
%F A188163 A004001(a(n)) = n and A004001(m) < n for m < a(n).
%F A188163 A051135(n) = a(n+1) - a(n).
%p A188163 A188163 := proc(n)
%p A188163     for a from 1 do
%p A188163         if A004001(a) = n then
%p A188163             return a;
%p A188163         end if;
%p A188163     end do:
%p A188163 end proc: # _R. J. Mathar_, May 15 2013
%t A188163 h[1] = 1; h[2] = 1; h[n_] := h[n] = h[h[n-1]] + h[n - h[n-1]];
%t A188163 a[n_] := For[m = 1, True, m++, If[h[m] == n, Return[m]]];
%t A188163 Array[a, 64] (* _Jean-François Alcover_, Jan 27 2018 *)
%o A188163 (Haskell)
%o A188163 import Data.List (elemIndex)
%o A188163 import Data.Maybe (fromJust)
%o A188163 a188163 n = succ $ fromJust $ elemIndex n a004001_list
%o A188163 (Scheme)
%o A188163 (define A188163 (RECORD-POS 1 1 A004001))
%o A188163 ;; Code for A004001 given in that entry. Uses also my IntSeq-library. - _Antti Karttunen_, Jan 18 2016
%o A188163 (Magma)
%o A188163 h:=[n le 2 select 1 else Self(Self(n-1)) + Self(n - Self(n-1)): n in [1..500]]; // h=A004001
%o A188163 A188163:= function(n)
%o A188163    for j in [1..2*n+1] do
%o A188163        if h[j] eq n then return j; end if;
%o A188163    end for;
%o A188163 end function;
%o A188163 [A188163(n): n in [1..100]]; // _G. C. Greubel_, May 20 2024
%o A188163 (SageMath)
%o A188163 @CachedFunction
%o A188163 def h(n): return 1 if (n<3) else h(h(n-1)) + h(n - h(n-1)) # h=A004001
%o A188163 def A188163(n):
%o A188163     for j in range(1,2*n+2):
%o A188163         if h(j)==n: return j
%o A188163 [A188163(n) for n in range(1,101)] # _G. C. Greubel_, May 20 2024
%Y A188163 Equal to A088359 with prepended 1.
%Y A188163 Column 1 of A265901, Row 1 of A265903.
%Y A188163 Cf. A051135 (first differences).
%Y A188163 Cf. A087686 (complement, apart from the initial 1).
%Y A188163 Cf. A004001 (also the least monotonic left inverse of this sequence).
%Y A188163 Cf. A093879, A265332.
%Y A188163 Cf. A266399 (a subsequence).
%K A188163 nonn
%O A188163 1,2
%A A188163 _Reinhard Zumkeller_, Jun 03 2011