login
Unique monotone sequence satisfying a(a(a(n))) = 2n.
3

%I #38 Feb 03 2024 10:12:26

%S 4,5,6,8,9,10,11,12,14,16,17,18,19,20,21,22,23,24,26,28,30,32,33,34,

%T 35,36,37,38,39,40,41,42,43,44,45,46,47,48,50,52,54,56,58,60,62,64,65,

%U 66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89

%N Unique monotone sequence satisfying a(a(a(n))) = 2n.

%C For k >= 1 and m >= 2, a monotone a(n) such that a^(k+1)(n) = m*n is unique only when m = 2 or (k,m) = (1,3).

%H Robert Israel, <a href="/A088720/b088720.txt">Table of n, a(n) for n = 3..10000</a>

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint, 2016.

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

%F For a^(k+1)(n) = 2n, we have for (k+1)2^m <= n <= (2k+1)2^m, a(n) = n+2^m; for (2k+1)2^m <= n <= (2k+2)2^m, a(n) = 2n-2k*2^m.

%F From _Robert Israel_, Apr 05 2017: (Start)

%F a(2n) = 2*a(n).

%F a(4n+1) = a(2n+1) + 2*a(n).

%F a(4n+3) = 3*a(2n+1) - 2*a(n).

%F G.f. g(z) satisfies g(z) = 4*z^3 + 5*z^4 + 2*z^5 - 3*z^7 + 5*z^9 - 4*z^11 + (2+1/(2*z)+3*z/2)*g(z^2) - (1/(2*z)+3*z/2)*g(-z^2) + (2*z-2*z^3)*g(z^4).

%F (End)

%e a(a(a(3))) = a(a(4)) = a(5) = 6.

%p seq(op([seq(n+2^m,n=3*2^m .. 5*2^m-1), seq(2*n-4*2^m, n=5*2^m..6*2^m-1)]), m=0..10); # _Robert Israel_, Apr 05 2017

%o (PARI) a(n)={my(m=logint(n/3, 2)); if(n<5*2^m, n+2^m, 2*(n-2^(m+1)))}; \\ _Yifan Xie_, Jan 31 2024

%Y Cf. A007378, A003605, A088721.

%K easy,nonn

%O 3,1

%A _Colin Mallows_, Oct 16 2003

%E More terms from _John W. Layman_, Oct 18 2003