A103391 "Even" fractal sequence for the natural numbers: Deleting every even-indexed term results in the same sequence.

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

Offset: 1

Author

Eric Rowland, Mar 20 2005

Keywords

• easy
• nonn

Comments

A003602 is the "odd" fractal sequence for the natural numbers.

Lexicographically earliest infinite sequence such that a(i) = a(j) => A348717(A005940(i)) = A348717(A005940(j)) for all i, j >= 1. A365718 is an analogous sequence related to A356867 (Doudna variant D(3)). - Antti Karttunen, Sep 17 2023

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..10000 from Reinhard Zumkeller)

Crossrefs

Cf. A003602, A005940, A025480, A220466, A286387, A353368 (Dirichlet inverse).

Cf. also A110962, A110963, A365718.

Differs from A331743(n-1) for the first time at n=192, where a(192) = 97, while A331743(191) = 23.

Differs from A351460.

Programs

Haskell

-- import Data.List (transpose)
a103391 n = a103391_list !! (n-1)
a103391_list = 1 : ks where
   ks = concat $ transpose [[2..], ks]
-- Reinhard Zumkeller, May 23 2013

Maple

nmax := 82: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 2 to ceil(nmax/(p+2))+1 do a((2*n-3)*2^p+1) := n od: od: a(1) := 1: seq(a(n), n=1..nmax); # Johannes W. Meijer, Jan 28 2013

Mathematica

a[n_] := ((n-1)/2^IntegerExponent[n-1, 2] + 3)/2; a[1] = 1; Array[a, 100] (* Amiram Eldar, Sep 24 2023 *)

PARI

A003602(n) = (n/2^valuation(n, 2)+1)/2; \\ From A003602
A103391(n) = if(1==n,1,(1+A003602(n-1))); \\ Antti Karttunen, Feb 05 2020

Python

def v(n): b = bin(n); return len(b) - len(b.rstrip("0"))
def b(n): return (n//2**v(n)+1)//2
def a(n): return 1 if n == 1 else 1 + b(n-1)
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, May 29 2022

Python

def A103391(n): return (n-1>>(n-1&-n+1).bit_length())+2 if n>1 else 1 # Chai Wah Wu, Jan 04 2024

Formula

For n > 1, a(n) = A003602(n-1) + 1. - Benoit Cloitre, May 26 2007, indexing corrected by Antti Karttunen, Feb 05 2020

a((2*n-3)*2^p+1) = n, p >= 0 and n >= 2, with a(1) = 1. - Johannes W. Meijer, Jan 28 2013

Sum_{k=1..n} a(k) ~ n^2/6. - Amiram Eldar, Sep 24 2023

Extensions

Data section extended up to a(105) (to better differentiate from several nearby sequences) by Antti Karttunen, Feb 05 2020