login
a(n) = A082007(n-1) + 1.
3

%I #14 May 16 2021 04:53:10

%S 1,2,3,4,7,10,13,5,6,8,9,11,12,14,15,16,31,46,61,76,91,106,121,136,

%T 151,166,181,196,211,226,241,17,18,32,33,47,48,62,63,77,78,92,93,107,

%U 108,122,123,137,138,152,153,167,168,182,183,197,198

%N a(n) = A082007(n-1) + 1.

%C From Steve Witham (sw(AT)tiac.net), Oct 13 2009: (Start)

%C Starting the sequence (and its index) at 1 (as in A082008) instead of 0 (as in A082007) seems more natural. This was conceived as a way to arrange a heapsort in memory to improve locality of reference. The classic Williams/Floyd heapsort also works a little more naturally when the origin is 1.

%C This sequence is a permutation of the integers >= 1. (End)

%C Moreover, the first 2^2^n - 1 terms are a permutation of the first 2^2^n - 1 positive integers. - _Ivan Neretin_, Mar 12 2017

%H Ivan Neretin, <a href="/A082008/b082008.txt">Table of n, a(n) for n = 1..8191</a>

%H Steve Witham, <a href="http://www.tiac.net/~sw/2009/10/Clumpy_heapsort">Clumpy Heapsort</a>

%H Steve Witham, <a href="http://www.tiac.net/~sw/2009/10/Clumpy_heapsort/">Clumpy Heapsort</a>. [From Steve Witham (sw(AT)tiac.net), Oct 13 2009]

%F May be defined recursively by:

%F def A082008( n ):

%F if n == 1: return 1

%F y = 2 ** int( log( n, 2 ) )

%F yc = 2 ** 2 ** int( log( log( y, 2 ), 2 ) )

%F yr = y / yc

%F return (yc-1) * int( (n-y) / yr + 1 ) + A082008( yr + n % yr ) (from Steve Witham, Oct 14 2009)

%t w = {{1}}; Do[k = 2^Floor@Log2[n - 1]; AppendTo[w, Flatten@Table[w[[n - k]] + (2^k - 1) i, {i, 2^k}]], {n, 2, 7}]; a = Flatten@w (* _Ivan Neretin_, Mar 12 2017 *)

%o (Python)

%o def A082008( n ):

%o if n == 1: return 1

%o y = 2 ** int( log( n, 2 ) )

%o yc = 2 ** 2 ** int( log( log( y, 2 ), 2 ) )

%o yr = y // yc

%o return (yc-1) * int( (n-y) / yr + 1 ) + A082008( yr + n % yr )

%o # Steve Witham (sw(AT)tiac.net), Oct 13 2009

%K nonn,tabf

%O 1,2

%A _N. J. A. Sloane_, Oct 06 2009, based on a posting by Steve Witham (sw(AT)tiac.net) to the Math Fun Mailing List, Sep 30 2009

%E The origin is 1 Steve Witham (sw(AT)tiac.net), Oct 13 2009