login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A082008 a(n) = A082007(n-1) + 1. 3
1, 2, 3, 4, 7, 10, 13, 5, 6, 8, 9, 11, 12, 14, 15, 16, 31, 46, 61, 76, 91, 106, 121, 136, 151, 166, 181, 196, 211, 226, 241, 17, 18, 32, 33, 47, 48, 62, 63, 77, 78, 92, 93, 107, 108, 122, 123, 137, 138, 152, 153, 167, 168, 182, 183, 197, 198 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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.

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

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

LINKS

Ivan Neretin, Table of n, a(n) for n = 1..8191

Steve Witham, Clumpy Heapsort

Steve Witham, Clumpy Heapsort. [From Steve Witham (sw(AT)tiac.net), Oct 13 2009]

FORMULA

May be defined recursively by:

def A082008( n ):

if n == 1: return 1

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

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

yr = y / yc

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

MATHEMATICA

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 *)

PROG

(Python) \D def A082008( n ):

..if n == 1: return 1

..

..y = 2 ** int( log( n, 2 ) )

..yc = 2 ** 2 ** int( log( log( y, 2 ), 2 ) )

..yr = y / yc

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

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

CROSSREFS

Sequence in context: A321684 A117220 A118426 * A105330 A097545 A202016

Adjacent sequences:  A082005 A082006 A082007 * A082009 A082010 A082011

KEYWORD

nonn,tabf

AUTHOR

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

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 10 12:19 EDT 2020. Contains 336379 sequences. (Running on oeis4.)