A131987 -id:A131987 - cp's OEIS frontend

A003602 Kimberling's paraphrases: if n = (2k-1)*2^m then a(n) = k.

1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, 5, 10, 3, 11, 6, 12, 2, 13, 7, 14, 4, 15, 8, 16, 1, 17, 9, 18, 5, 19, 10, 20, 3, 21, 11, 22, 6, 23, 12, 24, 2, 25, 13, 26, 7, 27, 14, 28, 4, 29, 15, 30, 8, 31, 16, 32, 1, 33, 17, 34, 9, 35, 18, 36, 5, 37, 19, 38, 10, 39, 20, 40, 3, 41, 21, 42

Offset: 1

N. J. A. Sloane, Mira Bernstein

Fractal sequence obtained from powers of 2.
k occurs at (2*k-1)*A000079(m), m >= 0. - Robert G. Wilson v, May 23 2006
Sequence is T^(oo)(1) where T is acting on a word w = w(1)w(2)..w(m) as follows: T(w) = "1"w(1)"2"w(2)"3"(...)"m"w(m)"m+1". For instance T(ab) = 1a2b3. Thus T(1) = 112, T(T(1)) = 1121324, T(T(T(1))) = 112132415362748. - Benoit Cloitre, Mar 02 2009
Note that iterating the post-numbering operator U(w) = w(1) 1 w(2) 2 w(3) 3... produces the same limit sequence except with an additional "1" prepended, i.e., 1,1,1,2,1,3,2,4,... - Glen Whitney, Aug 30 2023
In the binary expansion of n, first swallow all zeros from the right, then add 1, and swallow the now-appearing 0 bit as well. - Ralf Stephan, Aug 22 2013
Although A264646 and this sequence initially agree in their digit-streams, they differ after 48 digits. - N. J. A. Sloane, Nov 20 2015
"[This is a] fractal because we get the same sequence after we delete from it the first appearance of all positive integers" - see Cobeli and Zaharescu link. - Robert G. Wilson v, Jun 03 2018
From Peter Munn, Jun 16 2022: (Start)
The sequence is the list of positive integers interleaved with the sequence itself. Provided the offset is suitable (which is the case here) a term of such a self-interleaved sequence is determined by the odd part of its index. Putting some of the formulas given here into words, a(n) is the position of the odd part of n in the list of odd numbers.
Applying the interleaving transform again, we get A110963.
(End)
Omitting all 1's leaves A131987 + 1. - David James Sycamore, Jul 26 2022
a(n) is also the smallest positive number not among the terms between a(a(n-1)) and a(n-1) inclusive (with a(0)=1 prepended). - Neal Gersh Tolunsky, Mar 07 2023

			From _Peter Munn_, Jun 14 2022: (Start)
Start of table showing the interleaving with the positive integers:
   n  a(n)  (n+1)/2  a(n/2)
   1    1      1
   2    1               1
   3    2      2
   4    1               1
   5    3      3
   6    2               2
   7    4      4
   8    1               1
   9    5      5
  10    3               3
  11    6      6
  12    2               2
(End)

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Cristian Cobeli and Alexandru Zaharescu, Promenade around Pascal Triangle - Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104) No. 1, 2013, 73-98.
J.-P. Delahaye, La marelle arithmétique, Pour la Science, No. 360, October 2007. In French.
Dale Gerdemann, Plotting Adjacent Points in A003602, Kimberling's Paraphrase, YouTube Video, 2015.
Dale Gerdemann, Plotting Adjacent Terms of A003602 Modulo Increasing Powers of 2, YouTube Video, 2015.
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Clark Kimberling, Numeration systems and fractal sequences, Acta Arithmetica 73 (1995) 103-117.
Clark Kimberling, Fractal sequences
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Matty van-Son, Palindromic sequences of the Markov spectrum, arXiv:1804.10802 [math.NT], 2018.
Eric Weisstein's World of Mathematics, Odd Part
Index entries for sequences related to binary expansion of n

a(n) is the index of the column in A135764 where n appears (see also A054582).
Cf. A000079, A000265, A001511, A003603, A003961, A014577 (with offset 1, reduction mod 2), A025480, A035528, A048673, A101279, A110963, A117303, A126760, A181988, A220466, A249745, A253887, A337821 (2-adic valuation).
Cf. also A349134 (Dirichlet inverse), A349135 (sum with it), A349136 (Möbius transform), A349431, A349371 (inverse Möbius transform).
Cf. A065120, A131987.
Cf. A264646.
Cf. A123390, A118319.

a003602 = (`div` 2) . (+ 1) . a000265
-- Reinhard Zumkeller, Feb 16 2012, Oct 14 2010

import Data.List (transpose)
a003602 = flip div 2 . (+ 1) . a000265
a003602_list = concat $ transpose [[1..], a003602_list]
-- Reinhard Zumkeller, Aug 09 2013, May 23 2013

A003602:=proc(n) options remember: if n mod 2 = 1 then RETURN((n+1)/2) else RETURN(procname(n/2)) fi: end proc:
seq(A003602(n), n=1..83); # Pab Ter
nmax := 83: for m from 0 to ceil(simplify(log[2](nmax))) do for k from 1 to ceil(nmax/(m+2)) do a((2*k-1)*2^m) := k od: od: seq(a(k), k=1..nmax); # Johannes W. Meijer, Feb 04 2013
A003602 := proc(n)
    a := 1;
    for p in ifactors(n)[2] do
        if op(1,p) > 2 then
            a := a*op(1,p)^op(2,p) ;
        end if;
    end do  :
    (a+1)/2 ;
end proc: # R. J. Mathar, May 19 2016

a[n_] := Block[{m = n}, While[ EvenQ@m, m /= 2]; (m + 1)/2]; Array[a, 84] (* or *)
a[1] = 1; a[n_] := a[n] = If[OddQ@n, (n + 1)/2, a[n/2]]; Array[a, 84] (* Robert G. Wilson v, May 23 2006 *)
a[n_] := Ceiling[NestWhile[Floor[#/2] &, n, EvenQ]/2]; Array[a, 84] (* Birkas Gyorgy, Apr 05 2011 *)
a003602 = {1}; max = 7; Do[b = {}; Do[AppendTo[b, {k, a003602[[k]]}], {k, Length[a003602]}]; a003602 = Flatten[b], {n, 2, max}]; a003602 (* L. Edson Jeffery, Nov 21 2015 *)

A003602(n)=(n/2^valuation(n,2)+1)/2; /* Joerg Arndt, Apr 06 2011 */

import math
def a(n): return (n/2**int(math.log(n - (n & n - 1), 2)) + 1)/2 # Indranil Ghosh, Apr 24 2017

def A003602(n): return (n>>(n&-n).bit_length())+1 # Chai Wah Wu, Jul 08 2022

(define (A003602 n) (let loop ((n n)) (if (even? n) (loop (/ n 2)) (/ (+ 1 n) 2)))) ;; Antti Karttunen, Feb 04 2015

a(n) = (A000265(n) + 1)/2.
a((2*k-1)*2^m) = k, for m >= 0 and k >= 1. - Robert G. Wilson v, May 23 2006
Inverse Weigh transform of A035528. - Christian G. Bower
G.f.: 1/x * Sum_{k>=0} x^2^k/(1-2*x^2^(k+1) + x^2^(k+2)). - Ralf Stephan, Jul 24 2003
a(2*n-1) = n and a(2*n) = a(n). - Pab Ter (pabrlos2(AT)yahoo.com), Oct 25 2005
a(A118413(n,k)) = A002024(n,k); = a(A118416(n,k)) = A002260(n,k); a(A014480(n)) = A001511(A014480(n)). - Reinhard Zumkeller, Apr 27 2006
Ordinal transform of A001511. - Franklin T. Adams-Watters, Aug 28 2006
a(n) = A249745(A126760(A003961(n))) = A249745(A253887(A048673(n))). That is, this sequence plays the same role for the numbers in array A135764 as A126760 does for the odd numbers in array A135765. - Antti Karttunen, Feb 04 2015 & Jan 19 2016
G.f. satisfies g(x) = g(x^2) + x/(1-x^2)^2. - Robert Israel, Apr 24 2015
a(n) = A181988(n)/A001511(n). - L. Edson Jeffery, Nov 21 2015
a(n) = A025480(n-1) + 1. - R. J. Mathar, May 19 2016
a(n) = A110963(2n-1) = A349135(4*n). - Antti Karttunen, Apr 18 2022
a(n) = (1 + n)/2, for n odd; a(n) = a(n/2), for n even. - David James Sycamore, Jul 28 2022
a(n) = n/2^A001511(n) + 1/2. - Alan Michael Gómez Calderón, Oct 06 2023
a(n) = A123390(A118319(n)). - Flávio V. Fernandes, Mar 02 2025

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 25 2005

A025480 a(2n) = n, a(2n+1) = a(n).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 0, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10

Offset: 0

David W. Wilson

These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap. - R. K. Guy, Mar 30 2006. See Levine 2004/2006 for more about this. - N. J. A. Sloane, Aug 14 2016
When n > 0 is written as (2k+1)*2^j then k = a(n-1) and j = A007814(n), so: when n is written as (2k+1)*2^j-1 then k = a(n) and j = A007814(n+1), when n > 1 is written as (2k+1)*2^j+1 then k = a(n-2) and j = A007814(n-1). - Henry Bottomley, Mar 02 2000 [sequence id corrected by Peter Munn, Jun 22 2022]
According to the comment from Deuard Worthen (see Example section), this may be regarded as a triangle where row r=1,2,3,... has length 2^(r-1) and values T(r,2k-1)=T(r-1,k), T(r,2k)=2^(r-1)+k-1; i.e., previous row gives 1st, 3rd, 5th, ... term and 2nd, 4th, ... terms are numbers 2^(r-1),...,2^r-1 (i.e., those following the last one from the previous row). - M. F. Hasler, May 03 2008
Let StB be a Stern-Brocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n-1)<>0 and a(n)<>0 then mediant(StB(a(n-1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n-1)),Right) else mediant(Left,StB(a(n-1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). - Reinhard Zumkeller, Dec 22 2008
This sequence is the unique fixed point of the function (a(0), a(1), a(2), ...) |--> (0, a(0), 1, a(1), 2, a(2), ...) which interleaves the nonnegative integers between the elements of a sequence. - Cale Gibbard (cgibbard(AT)gmail.com), Nov 18 2009
Also the number of remaining survivors in a Josephus problem after the person originally first in line has been eliminated (see A225381). - Marcus Hedbring, May 18 2013
A fractal sequence - see Levine 2004/2006. - N. J. A. Sloane, Aug 14 2016
From David James Sycamore, Apr 29 2020: (Start)
One of a family of fractal sequences, S_k; defined as follows for k >= 2: a(k*n) = n, a(k*n+r) = a((k-1)*n + (r-1)), r = 1..(k-1). S_2 is A025480; S_3 gives: a(3*n) = n, a(3*n + 1) = a(2*n), a(3*n + 2) = a(2*n + 1), which is A263390.
The subsequence of all nonzero terms is A131987. (End)
Similar to but different from A108202. - N. J. A. Sloane, Nov 26 2020
This sequence can be otherwise defined in two alternative (but related) ways, with a(0)=0, as follows: (i) If a(n) is a novel term, then a(n+1) = a(a(n)); if a(n) has been seen before, most recently at a(m), then a(n+1) = n-m (as in A181391). (ii) As above for novel a(n), then if a(n) has been seen before, a(n+1) = smallest k < a(n) which is not already a term. - David James Sycamore, Jul 13 2021
From a binary perspective, the sequence can be seen as even,odd pairs where the odd value is the previous even value, dropping the rightmost bits up to and including the lowest zero bit, aka right-shifted past the lowest clear bit. E.g., (5)101 -> 1, (17)10001 -> (4)100, (29)11101 -> (7)111, (39)100111 -> (2)10. - Joe Nellis, Oct 09 2022

			From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)
The sequence can be constructed as a triangle as:
  0
  0  1
  0  2  1  3
  0  4  2  5  1  6  3  7
  0  8  4  9  2 10  5 11  1 12  6 13  3 14  7 15
  ...
At each stage we interleave the next 2^m numbers in the previous row. (End)
Left=0/1, Right=1/0: StB=A007305/A047679; Left=0/1, Right=1/1: StB=A007305/A007306; Left=1/3, Right=2/3: StB=A153161/A153162. - _Reinhard Zumkeller_, Dec 22 2008

L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
Ralf Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.4.
L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Ralf Stephan, Some divide-and-conquer sequences ....
Ralf Stephan, Table of generating functions.
Paul Tarau, A Groupoid of Isomorphic Data Transformations, Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
Index entries for sequences related to the Josephus Problem.

The Y-projection of A075300.

Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381, A131987, A263390, A181391, A007814.

import Data.List
interleave xs ys = concat . transpose $ [xs,ys]
a025480 = interleave [0..] a025480
-- Cale Gibbard, Nov 18 2009

Cf. comments by Worthen and Hasler.
import Data.List (transpose)
a025480 n k = a025480_tabf !! n !! k
a025480_row n = a025480_tabf !! n
a025480_tabf = iterate (\xs -> concat $
   transpose [xs, [length xs .. 2 * length xs - 1]]) [0]
a025480_list = concat $ a025480_tabf
-- Reinhard Zumkeller, Apr 29 2012

A025480 := proc(n)
    option remember ;
    if type(n,'even') then
        n/2 ;
    else
        procname((n-1)/2) ;
    end if;
end proc:
seq(A025480(n),n=0..100) ; # R. J. Mathar, Jul 16 2020

a[n_] := a[n] = If[OddQ@n, a[(n - 1)/2], n/2]; Table[ a[n], {n, 0, 83}] (* Robert G. Wilson v, Mar 30 2006 *)
Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* IWABUCHI Yu(u)ki, Oct 13 2012 *)

a(n)={while(n%2,n\=2);n\2} \\ M. F. Hasler, May 03 2008

A025480(n)=n>>valuation(n*2+2,2) \\ M. F. Hasler, Apr 12 2012

def A025480(n): return n>>((~(n+1)&n).bit_length()+1) # Chai Wah Wu, Jul 13 2022

A025480 = lambda n: odd_part(n+1)//2
[A025480(n) for n in (0..83)] # Peter Luschny, May 20 2014

a(n) = A003602(n+1) - 1. [Corrected by Max Alekseyev, May 05 2022]
a(n) = (A000265(n+1)-1)/2 = ((n+1)/A006519(n+1)-1)/2.
a(n) = A153733(n)/2. - Reinhard Zumkeller, Dec 31 2008
2^A007814(n+1)*(2*a(n)+1) = n+1. (See functions hd, tl and cons in [Paul Tarau 2009].) - Paul Tarau (paul.tarau(AT)gmail.com), Mar 21 2010
a(3*n + 1) = A173732(n). - Reinhard Zumkeller, Apr 29 2012
a((2*n+1)*2^p-1) = n, p >= 0 and n >= 0. - Johannes W. Meijer, Jan 24 2013
a(n) = n - A225381(n). - Marcus Hedbring, May 18 2013
G.f.: -1/(1-x) + Sum_{k>=0} x^(2^k-1)/(1-2*x^2^(k+1)+x^2^(k+2)). - Ralf Stephan, May 19 2013
a(n) = A049084(A181363(n+1)). - Reinhard Zumkeller, Mar 22 2014
a(n) = floor(n / 2^A001511(n+1)). - Adam Shelly, Mar 05 2019
Recursion: a(0) = 0; a(n + 1) = a(a(n)) if a(n) is a first occurrence of a term, else a(n + 1) = n - a(n-1). - David James Sycamore, Apr 29 2020
a(n) * 2^(A007814(n+1)+1) + 2^A007814(n+1) - 1 = n (equivalent to the formula given in the comment by Paul Tarau). - Ruud H.G. van Tol, Apr 14 2023
Sum_{k=1..n} a(k) = n^2/6 + O(n). - Amiram Eldar, Aug 07 2023

Edited by M. F. Hasler, Mar 16 2018

A133108 Representation of a dense para-sequence.

Original entry on oeis.org

1, 2, 3, 4, 1, 5, 6, 2, 7, 8, 9, 10, 3, 11, 12, 4, 13, 14, 1, 15, 16, 5, 17, 18, 6, 19, 20, 2, 21, 22, 7, 23, 24, 8, 25, 26, 27, 28, 9, 29, 30, 10, 31, 32, 3, 33, 34, 11, 35, 36, 12, 37, 38, 4, 39, 40, 13, 41, 42, 14, 43, 44, 1, 45, 46, 15, 47, 48, 16, 49, 50, 5, 51, 52, 17, 53, 54, 18

Offset: 1

Clark Kimberling, Sep 12 2007

nonn

(1) A fractal sequence. (2) The para-sequence may be regarded as a sort of "limit" of the concatenated segments. The para-sequence (itself not a sequence) is dense in the sense that every pair of terms i and j are separated by another term (and hence separated by infinitely many terms). (3) The para-sequence accounts for positions of triadic rational numbers in the following way: 1/3 < 2/3 matches the segment 1,2; 1/9 < 2/9 < 1/3 < 4/9 < 5/9 < 2/3 < 7/9 < 8/9 matches the segment 3,4,1,5,6,2,7,8, etc.

			The first segment is 1,2; the 2nd is 3,4,1,5,6,2,7,8; the 4th begins with 27,28,9 and ends with 26,79,80.

Clark Kimberling, Proper self-containing sequences, fractal sequences and para-sequences, preprint, 2007.

Clark Kimberling, Table of n, a(n) for n = 1..10000
Clark Kimberling, Self-Containing Sequences, Selection Functions, and Parasequences, J. Int. Seq. Vol. 25 (2022), Article 22.2.1.

Cf. A131987.

Flatten@NestList[Riffle[Range[Length[#] + 1, 3 Length[#] + 2], #, 3] &, {1, 2}, 3] (* Birkas Gyorgy, Mar 11 2011 *)

cp's OEIS Frontend

A269752 Table of inverse permutations of the rows of A131987: Position of numbers inserted in "storage order" into a perfect binary table of 2^k-1 nodes.

Views

Author

Keywords

Comments

Examples

Programs

PARI

A003602 Kimberling's paraphrases: if n = (2k-1)*2^m then a(n) = k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A025480 a(2n) = n, a(2n+1) = a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A133108 Representation of a dense para-sequence.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica