login
Smallest m such that A004001(m) = n.
15

%I #56 May 21 2024 01:16:59

%S 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 43,44,46,49,50,52,55,59,65,66,67,68,69,70,72,73,74,75,77,78,79,81,82,

%U 84,87,88,89,91,92,94,97,98,100,103,107,108,110,113,117,122

%N Smallest m such that A004001(m) = n.

%C How is this related to A088359? - _R. J. Mathar_, Jan 09 2013

%C 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 From _Antti Karttunen_, Jan 10 & 18 2016: (Start)

%C Positions of records in A004001. After 1 the positions where A004001 increases (by necessity by one).

%C 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 Obviously A004001 can obtain unique values only at points which form a subset (A266399) of this sequence.

%C (End)

%H Reinhard Zumkeller, <a href="/A188163/b188163.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html">Hofstadter-Conway $10,000 Sequence.</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Hofstadter_sequence">Hofstadter sequence</a>

%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>

%F Other identities. For all n >= 1:

%F A004001(a(n)) = n and A004001(m) < n for m < a(n).

%F A051135(n) = a(n+1) - a(n).

%p A188163 := proc(n)

%p for a from 1 do

%p if A004001(a) = n then

%p return a;

%p end if;

%p end do:

%p end proc: # _R. J. Mathar_, May 15 2013

%t h[1] = 1; h[2] = 1; h[n_] := h[n] = h[h[n-1]] + h[n - h[n-1]];

%t a[n_] := For[m = 1, True, m++, If[h[m] == n, Return[m]]];

%t Array[a, 64] (* _Jean-François Alcover_, Jan 27 2018 *)

%o (Haskell)

%o import Data.List (elemIndex)

%o import Data.Maybe (fromJust)

%o a188163 n = succ $ fromJust $ elemIndex n a004001_list

%o (Scheme)

%o (define A188163 (RECORD-POS 1 1 A004001))

%o ;; Code for A004001 given in that entry. Uses also my IntSeq-library. - _Antti Karttunen_, Jan 18 2016

%o (Magma)

%o h:=[n le 2 select 1 else Self(Self(n-1)) + Self(n - Self(n-1)): n in [1..500]]; // h=A004001

%o A188163:= function(n)

%o for j in [1..2*n+1] do

%o if h[j] eq n then return j; end if;

%o end for;

%o end function;

%o [A188163(n): n in [1..100]]; // _G. C. Greubel_, May 20 2024

%o (SageMath)

%o @CachedFunction

%o def h(n): return 1 if (n<3) else h(h(n-1)) + h(n - h(n-1)) # h=A004001

%o def A188163(n):

%o for j in range(1,2*n+2):

%o if h(j)==n: return j

%o [A188163(n) for n in range(1,101)] # _G. C. Greubel_, May 20 2024

%Y Equal to A088359 with prepended 1.

%Y Column 1 of A265901, Row 1 of A265903.

%Y Cf. A051135 (first differences).

%Y Cf. A087686 (complement, apart from the initial 1).

%Y Cf. A004001 (also the least monotonic left inverse of this sequence).

%Y Cf. A093879, A265332.

%Y Cf. A266399 (a subsequence).

%K nonn

%O 1,2

%A _Reinhard Zumkeller_, Jun 03 2011