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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

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)

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 December 6 04:20 EST 2021. Contains 349562 sequences. (Running on oeis4.)