A007583 -id:A007583 - cp's OEIS frontend

A075677 Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.

1, 5, 1, 11, 7, 17, 5, 23, 13, 29, 1, 35, 19, 41, 11, 47, 25, 53, 7, 59, 31, 65, 17, 71, 37, 77, 5, 83, 43, 89, 23, 95, 49, 101, 13, 107, 55, 113, 29, 119, 61, 125, 1, 131, 67, 137, 35, 143, 73, 149, 19, 155, 79, 161, 41, 167, 85, 173, 11, 179, 91, 185, 47, 191, 97, 197

Offset: 1

T. D. Noe, Sep 25 2002

The even-indexed terms a(2i+2) = 6i+5 = A016969(i), i >= 0 [Comment corrected by Bob Selcoe, Apr 06 2015]. The odd-indexed terms are the same as A067745. Note that this sequence is A016789 with all factors of 2 removed from each term. Also note that a(4i-1) = a(i). No multiple of 3 is in this sequence. See A075680 for the number of iterations of R required to yield 1.
From Bob Selcoe, Apr 06 2015: (Start)
All numbers in this sequence appear infinitely often.
From Eq. 1 and Eq. 2 in Formulas: Eq. 1 is used with 1/3 of the numbers in this sequence, Eq. 2 is used with 2/3 of the numbers.
(End)
Empirical: For arbitrary m, Sum_{n=2..A007583(m)} (a(n) - a(n-1)) = 0. - Fred Daniel Kline, Nov 23 2015
From Wolfdieter Lang, Dec 07 2021: (Start)
Only positive numbers congruent to 1 or 5 modulo 6 appear.
i) For the sequence entry with value A016921(m), for m >= 0, that is, a value from {1, 7, 13, ...}, the indices n are given by the row of array A178415(2*m+1, k), for k >= 1.
ii) For the sequence entry with value A007528(m), for m >= 1, that is, a value from {5, 11, 17, ...}, the indices n are given by the row of array A178415(2*m, k), for k >= 1.
See also the array A347834 with permuted row numbers and columns k >= 0. (End)

			a(11) = 1 because 21 is the 11th odd number and R(21) = 64/64 = 1.
From _Wolfdieter Lang_, Dec 07 2021: (Start)
i) 1 (mod 6) entry 1 = A016921(0) appears for n = A178415(1, k) = A347834(1, k-1) (the arrays), for k >= 1, that is, for {1, 5, 21, ..} = A002450.
ii) 5 (mod 6) entry 11 = A007528(2) appears for n = A178415(4, k) = A347835(3, k-1) (the arrays), for k >= 1, that is, for {7, 29, 117, ..} = A072261. (End)

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E16, pp. 330-336.
Victor Klee and Stan Wagon, Old and new unsolved problems in plane geometry and number theory, The Mathematical Association of America, 1991, p. 225, C(2n+1) = a(n+1), n >= 0.
Jeffrey C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 57, also (90-9), p. 306.

T. D. Noe, Table of n, a(n) for n = 1..1000
Marc Chamberland, Una actualizacio del problema 3x + 1, Butl. Soc. Catalana Mat. (18), 19-45, 2003.
Jeffrey C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Fabian S. Reid, The Visual Pattern in the Collatz Conjecture and Proof of No Non-Trivial Cycles, arXiv:2105.07955 [math.GM], 2021.
Eric Weisstein's World of Mathematics, Collatz Problem.
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A000265, A000302, A002450, A007528, A016789, A016921, A016969, A065677, A072197, A072261, A075680, A081294, A178415, A191669, A329480, A347834.
Cf. A006370, A014682 (for non-reduced Collatz maps), A087230 (A371093), A371094.
Odd bisection of A139391.
Even bisection of A067745, which is also the odd bisection of this sequence.
After the initial 1, the second leftmost column of A256598.
Row 2 of A372283.

a075677 = a000265 . subtract 2 . (* 6) -- Reinhard Zumkeller, Jan 08 2014

f:=proc(n) local t1;
if n=1 then RETURN(1) else
t1:=3*n+1;
while t1 mod 2 = 0 do t1:=t1/2; od;
RETURN(t1); fi;
end;
# N. J. A. Sloane, Jan 21 2011

nextOddK[n_] := Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; (* assumes odd n *) Table[nextOddK[n], {n, 1, 200, 2}]
v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; Table[f[2*n - 1], {n, 66}] (* L. Edson Jeffery, May 06 2015 *)

a(n)=n+=2*n-1;n>>valuation(n,2) \\ Charles R Greathouse IV, Jul 05 2013

from sympy import divisors
def a(n):
    return max(d for d in divisors(n) if d % 2)
print([a(6*n - 2) for n in range(1, 101)]) # Indranil Ghosh, Apr 15 2017, after formula by Reinhard Zumkeller

a(n) = A000265(6*n-2) = A000265(3*n-1). - Reinhard Zumkeller, Jan 08 2014
From Bob Selcoe, Apr 05 2015: (Start)
For all n>=1 and for every k, there exists j>=0 dependent upon n and k such that either:
Eq. 1: a(n) = (3n-1)/2^(2j+1) when k = ((4^(j+1)-1)/3) mod 2^(2j+3). Alternatively: a(n) = A016789(n-1)/A081294(j+1) when k = A002450(j+1) mod A081294(j+2). Example: n=51; k=101 == 5 mod 32, j=1. a(51) = 152/8 = 19.
  or
Eq. 2: a(n) = (3n-1)/4^j when k = (5*2^(2j+1) - 1)/3 mod 4^(j+1). Alternatively: a(n) = A016789(n-1)/A000302(j) when k = A072197(j) mod A000302(j+1). Example: n=91; k=181 == 53 mod 64, j=2. a(91) = 272/16 = 17.
(End) [Definition corrected by William S. Hilton, Jul 29 2017]
a(n) = a(n + g*2^r) - 6*g, n > -g*2^r. Examples: n=59; a(59)=11, r=5. g=-1: 11 = a(27) = 5 - (-1)*6; g=1: 11 = a(91) = 17 - 1*6; g=2: 11 = a(123) = 23 - 2*6; g=3: 11 = a(155) = 29 - 3*6; etc. - Bob Selcoe, Apr 06 2015
a(n) = a((1 + (3*n - 1)*4^(k-1))/3), k>=1 (cf. A191669). - L. Edson Jeffery, Oct 05 2015
a(n) = a(4n-1). - Bob Selcoe, Aug 03 2017
a(n) = A139391(2n-1). - Antti Karttunen, May 06 2024
Sum_{k=1..n} a(k) ~ n^2. - Amiram Eldar, Aug 26 2024
G.f.: Sum_{k>=1} ((3 + 2*(-1)^k)*x^(3*2^(k - 1) - (-2)^k/3 + 1/3) + (3 - 2*(-1)^k)*x^(2^(k - 1) - (-2)^k/3 + 1/3))/(x^(2^k) - 1)^2. - Miles Wilson, Oct 26 2024

A047849 a(n) = (4^n + 2)/3.

Original entry on oeis.org

1, 2, 6, 22, 86, 342, 1366, 5462, 21846, 87382, 349526, 1398102, 5592406, 22369622, 89478486, 357913942, 1431655766, 5726623062, 22906492246, 91625968982, 366503875926, 1466015503702, 5864062014806, 23456248059222, 93824992236886, 375299968947542

Offset: 0

Clark Kimberling

Counts closed walks of length 2n at a vertex of the cyclic graph on 6 nodes C_6. - Paul Barry, Mar 10 2004
The number of closed walks of odd length of the cyclic graph is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011
A. A. Ivanov conjectures that the dimension of the universal embedding of the unitary dual polar space DSU(2n,4) is a(n). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004
Permutations with two fixed points avoiding 123 and 132.
Related to A024495(6n), A131708(6n+2), A024493(6n+4). First differences give A000302. - Paul Curtz, Mar 25 2008
Also the number of permutations of length n which avoid 4321 and 4123 (or 4321 and 3412, or 4123 and 3214, or 4123 and 2143). - Vincent Vatter, Aug 17 2009; minor correction by Henning Ulfarsson, May 14 2017
This sequence is related to A014916 by A014916(n) = n*a(n)-Sum_{i=0..n-1} a(i). - Bruno Berselli, Jul 27 2010, Mar 02 2012
For n >= 2, a(n) equals 2^n times the permanent of the (2n-2) X (2n-2) tridiagonal matrix with 1/sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
For n > 0, counts closed walks of length (n) at a vertex of a triangle with two (x2) loops at each vertex. - David Neil McGrath, Sep 11 2014
From Michel Lagneau, Feb 26 2015: (Start)
a(n) is also the sum of the largest odd divisors of the integers 1,2,3, ..., 2^n.
Proof:
All integers of the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} are of the form 2^k(2m+1) where k and m integers. The greatest odd divisor of a such integer is 2m+1. Reciprocally, if 2m+1 is an odd integer <= 2^n, there exists a unique integer in the set {2^(n-1)+1, 2^(n-1)+2, ..., 2^n} where 2m+1 is the greatest odd divisor. Hence the recurrence relation:
   a(n) = a(n+1) + (1 + 3 + ... + 2*2^(n-1) - 1) = a(n-1) + 4^(n-1) for n >= 2.
We obtain immediately: a(n) = a(1) + 4 + ... + 4^n = (4^n+2)/3. (End)
The number of Riordan graphs of order n+1. See Cheon et al., Proposition 2.8. - Peter Bala, Aug 12 2021
Let q = 2^(2n+1) and Omega_n be the Suzuki ovoid with q^2 + 1 points. Then a(n) is the number of orbits of the finite Suzuki group Sz(q) on 3-subsets of Omega_n. Link to result in References. - Paul M. Bradley, Jun 04 2023
Also the cogrowth sequence for the 8-element dihedral group D8 = . - Sean A. Irvine, Nov 04 2024

			a(2) = 6 for the number of round trips in C_6 from the six round trips from, say, vertex no. 1: 12121, 16161, 12161, 16121, 12321 and 16561. - _Wolfdieter Lang_, Nov 08 2011

Bruno Berselli, Table of n, a(n) for n = 0..1000
Jeffrey M. Barnes, Georgia Benkart, and Tom Halverson, McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 37-51.
Pascal Caron, Jean-Gabriel Luque, and Bruno Patrou, A combinatorial approach for the state complexity of the Shuffle product, arXiv:1905.08120 [cs.FL], 2019.
Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, and Seyed Ahmad Mojallal, Riordan graphs I: structural properties, Linear Algebra and its Applications, 579. pp. 89-135, Prop. 2.8. (2019).
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48. See Conjecture 5.5.
Kittitat Iamthong, Ji-Hwan Jung, and Sergey Kitaev, Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations, arXiv:2009.01410 [math.CO], 2020.
D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Mathematics 268 (2003), 171-183.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002.
Wikipedia, Permutation classes avoiding two patterns of length 4.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A000302, A001045, A002450, A007583, A024493, A047848, A078008, A121314, A131708, A178789, A199571.

Cf. A014916, A073724, A020988, A039301.

[(4^n+2)/3: n in [0..30]]; // Vincenzo Librandi, Dec 07 2015

(4^Range[0,30] +2)/3 (* or *) LinearRecurrence[{5,-4},{1,2},30] (* Harvey P. Dale, Nov 27 2015 *)

PARI
```
a(n)=(4^n+2)/3;
```

def A047849(n): return (pow(4, n) +2)//3
print([A047849(n) for n in range(41)]) # G. C. Greubel, Jan 17 2025

def A047849(n): return ((1 << (2 * n)) + 2) // 3 # John Reimer Morales, Aug 05 2025

n-th difference of a(n), a(n-1), ..., a(0) is 3^(n-1) for n >= 1.
From Henry Bottomley, Aug 29 2000: (Start)
a(n) = (4^n + 2)/3.
a(n) = 4*a(n-1) - 2.
a(n) = 5*a(n-1) - 4*a(n-2).
a(n) = 2*A007583(n-1) = A002450(n) + 1. (End)
a(n) = A047848(1,n).
With interpolated zeros, this is (-2)^n/6 + 2^n/6 + (-1)^n/3 + 1/3. - Paul Barry, Aug 26 2003
a(n) = A007583(n) - A002450(n) = A001045(2n+1) - A001045(2n) . - Philippe Deléham, Feb 25 2004
Second binomial transform of A078008. Binomial transform of 1, 1, 3, 9, 81, ... (3^n/3 + 2*0^n/3). a(n) = A078008(2n). - Paul Barry, Mar 14 2004
G.f.: (1-3*x)/((1-x)*(1-4*x)). - Herbert Kociemba, Jun 06 2004
a(n) = Sum_{k=0..n} 2^k*A121314(n,k). - Philippe Deléham, Sep 15 2006
a(n) = (A001045(2*n+1) + 1)/2. - Paul Barry, Dec 05 2007
From Bruno Berselli, Jul 27 2010: (Start)
a(n) = (A020988(n) + 2)/2 = A039301(n+1)/2.
Sum_{i=0..n} a(i) = A073724(n). (End)
For n >= 3, a(n) equals [2, 1, 1; 1, 2, 1; 1, 1, 2]^(n - 2)*{1, 1, 2}*{1, 1, 2}. - John M. Campbell, Jul 09 2011
a(n) = Sum_{k=0..n} binomial(2*n, mod(n,3) + 3*k). - Oboifeng Dira, May 29 2020
From Elmo R. Oliveira, Dec 21 2023: (Start)
E.g.f.: (exp(x)*(exp(3*x) + 2))/3.
a(n) = A178789(n+1)/3. (End)
a(n) = A000302(n) - A020988(n). - John Reimer Morales, Aug 03 2025

New name from Charles R Greathouse IV, Dec 22 2011

A072197 a(n) = 4*a(n-1) + 1 with a(0) = 3.

Original entry on oeis.org

3, 13, 53, 213, 853, 3413, 13653, 54613, 218453, 873813, 3495253, 13981013, 55924053, 223696213, 894784853, 3579139413, 14316557653, 57266230613, 229064922453, 916259689813, 3665038759253, 14660155037013, 58640620148053, 234562480592213, 938249922368853, 3752999689475413

Offset: 0

N. Rathankar (rathankar(AT)yahoo.com), Jul 03 2002

Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := 2, (i > 1), A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n - 1) = (-1)^n*charpoly(A, -2). - Milan Janjic, Jan 26 2010
Numbers whose binary representation is 11 together with n times 01. For example, 213 = 11010101 (2). - Omar E. Pol, Nov 22 2012
The Collatz-function starting with a(n) will terminate at 1 after 2*n + 7 steps. This is because 3*a(n) + 1 = 5*2^(2n + 1), and the Collatz-function starting with 5 terminates at 1 after 5 additional steps.  So for example, a(2) = 53; Collatz sequence starting with 53 follows: 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (11 steps). - Bob Selcoe, Apr 03 2015
a(n) is also the sum of the numerator and denominator of the binary fractions 0.1, 0.101, 0.10101, 0.1010101... Thus 0.1 = 1/2 with 1 + 2 = 3, 0.101 = 1/2 + 1/8 = 5/8 with 5 + 8 = 13; 0.10101 = 1/2 + 1/8 + 1/32 = 21/32 with 21 + 32 = 53. - J. M. Bergot, Sep 28 2016
a(n), for n >= 2, is also the smallest odd number congruent to 5 modulo 8 for which the modified reduced Collatz map given in A324036 has n consecutive extra steps compared to the reduced Collatz map given in A075677. - Nicolas Vaillant, Philippe Delarue, Wolfdieter Lang, May 09 2019

			a(1) = 13 because a(0) = 3 and 4 * 3 + 1 = 13.
a(2) = 53 because a(1) = 13 and 4 * 13 + 1 = 53.
a(3) = 213 because a(2) = 53 and 4 * 53 + 1 = 213.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Petro Kosobutskyy and Volodymyr Karkulovskyy, Recurrence and structuring of sequences of transformations 3n+ 1 as arguments for confirmation of the Collatz hypothesis, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, pp. 28-33. See p. 29.
Petro Kosobutskyy, Anastasiia Yedyharova, and Taras Slobodzyan, From Newton's binomial and Pascal's triangle to Collatz's problem, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, pp. 121-127.
Index entries for linear recurrences with constant coefficients, signature (5,-4).
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A000302, A002066 (first differences), A002450, A007583, A020988, A075677, A178415, A324036, A347834.

[(10*4^n-1)/3: n in [0..30]]; // Vincenzo Librandi, Oct 31 2011

A072197:=n->(10*4^n - 1)/3: seq(A072197(n), n=0..30); # Wesley Ivan Hurt, Sep 29 2016

Table[(10(4^n) - 1)/3, {n, 0, 19}] (* Alonso del Arte, Nov 22 2012 *)
NestList[4#+1&,3,30] (* Harvey P. Dale, Mar 09 2019 *)

a(n)=10*4^n\3 \\ Charles R Greathouse IV, Apr 06 2016

Vec((3-2*x)/((1-x)*(1-4*x)) + O(x^30)) \\ Colin Barker, Sep 28 2016

a(n) = (10*4^n - 1)/3 = 10*A002450(n) + 3. - Henry Bottomley, Dec 02 2002
a(n) = 5*a(n-1) - 4*a(n-2), n > 1. - Vincenzo Librandi, Oct 31 2011
a(n) = 2^(2*(n + 1)) - (2^(2*n + 1) + 1)/3 = A000302(n + 1) - A007583(n). - Vladimir Pletser, Apr 12 2014
a(n) = (5*2^(2*n + 1) - 1)/3. - Bob Selcoe, Apr 03 2015
G.f.: (3-2*x)/((1-x)*(1-4*x)). - Colin Barker, Sep 28 2016
a(n) = A020988(n) + A020988(n+1) + 1 = 2*(A002450(n) + A002450(n+1)) + 1. - Yosu Yurramendi, Jan 24 2017
a(n) = A002450(n+1) + 2^(2*n+1). - Adam Michael Bere, May 13 2021
a(n) = a(n-1) + 5*2^(2*n-1), for n >= 1, with a(0) = 3. - Wolfdieter Lang, Aug 16 2021
a(n) = A178415(2,n+1) = A347834(2,n), arrays, for n >= 0. - Wolfdieter Lang, Nov 29 2021
E.g.f.: exp(x)*(10*exp(3*x) - 1)/3. - Elmo R. Oliveira, Apr 02 2025

More terms from Henry Bottomley, Dec 02 2002

A000979 Wagstaff primes: primes of form (2^p + 1)/3.

Original entry on oeis.org

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243, 62357403192785191176690552862561408838653121833643

Offset: 1

N. J. A. Sloane

nonn

Also, the primes with prime indices in the Jacobsthal sequence A001045.
Indices n such that (2^n + 1)/3 is prime are listed in A000978. - Alexander Adamchuk, Oct 03 2006
Primes in A126614. - Omar E. Pol, Nov 05 2013

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..20
P. Berrizbeitia, F. Luca, and R. Melham, On a compositeness test for (2^p+1)/3, JIS 13 (2010) 10.1.7
C. Caldwell's The Top Twenty, Wagstaff.
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
Editor's Note, Table of Wagstaff primes sent by D. H. Lehmer, Math. Mag., 27 (1954), 156-157.
Editor's Note, Table of Wagstaff primes sent by D. H. Lehmer (annotated and scanned copy)
Djurre G. Sikkema, Probable primality testing for Wagstaff prime, Bachelor's project mathematics, Univ. Groningen (Netherlands 2024). See p. 32.
S. S. Wagstaff, Jr., The Cunningham Project.
Wikipedia, Wagstaff prime

Cf. A000978, A049883, A001045, A127962.

Cf. A010051; subsequence of A007583.

a000979 n = a000979_list !! (n-1)
a000979_list = filter ((== 1) . a010051) a007583_list
-- Reinhard Zumkeller, Mar 24 2013

Select[ Array[(2^# + 1)/3 &, 190], PrimeQ] (* Vladimir Joseph Stephan Orlovsky, Apr 03 2010 *)

forprime(p=2,10000,if(ispseudoprime(2^p\/3),print1(2^p\/3,","))) \\ Edward Jiang, Sep 05 2014

from gmpy2 import divexact
from sympy import prime, isprime
A000979 = [p for p in (divexact(2**prime(n)+1,3) for n in range(2,10**2)) if isprime(p)] # Chai Wah Wu, Sep 04 2014

A087289 a(n) = 2^(2*n+1) + 1.

Original entry on oeis.org

3, 9, 33, 129, 513, 2049, 8193, 32769, 131073, 524289, 2097153, 8388609, 33554433, 134217729, 536870913, 2147483649, 8589934593, 34359738369, 137438953473, 549755813889, 2199023255553, 8796093022209, 35184372088833, 140737488355329, 562949953421313, 2251799813685249

Offset: 0

W. Edwin Clark, Aug 29 2003

Number of pairs of polynomials (f,g) in GF(2)[x] satisfying deg(f) <= n, deg(g) <= n and gcd(f,g) = 1.
An unpublished result due to Stephen Suen, David desJardins, and W. Edwin Clark. This is the case k = 2, q = 2 of their formula q^((n+1)*k) * (1 - 1/q^(k-1) + (q-1)/q^((n+1)*k)) for the number of ordered k-tuples (f_1, ..., f_k) of polynomials in GF(q)[x] such that deg(f_i) <= n for all i and gcd(f_1, ..., f_k) = 1.
Apparently the same as A084508 shifted left.
Terms in binary are palindromes of the form 1x1 where x is a string of 2*n zeros (A152577). - Brad Clardy, Sep 01 2011
For n > 0, a(n) is the number k such that the number of iterations of the map k -> (3k +1)/8 == 4 (mod 8) until reaching (3k +1)/8 <> 4 (mod 8) equals n. (see the Collatz problem: the start of the parity trajectory of a(n) is n times {100} = 100100100100...100abcd...). - Michel Lagneau, Jan 23 2012
An Engel expansion of 2 to the base 4 as defined in A181565, with the associated series expansion 2 = 4/3 + 4^2/(3*9) + 4^3/(3*9*33) + 4^4/(3*9*33*129) + .... Cf. A199561 and A207262. - Peter Bala, Oct 29 2013
For x = A083420(n), y = A000079(n+1), z = a(n) then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014
A254046(n+1) is the 3-adic valuation of a(n). - Fred Daniel Kline, Jan 11 2017

			a(0) = 3 since there are three pairs, (0,1), (1,0) and (1,1) of polynomials (f,g) in GF(2)[x] of degree at most 0 such that gcd(f,g) = 1.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
K. Morrison, Random polynomials over finite fields.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A087290, A087291, A087292, A099393.
Equals A004171 + 1.
Cf. also A007583, A181565, A199561, A207262, A254046, A283070.
Cf. A000079, A083420, A084508, A152577.

[2^(2*n+1) + 1: n in [0..30]]; // Vincenzo Librandi, May 16 2011

Table[2^(2 n + 1) + 1, {n, 0, 20}] (* or *) 3 NestList[4 # - 1 &, 1, 20]
(* or *) CoefficientList[Series[(3 - 6 x)/((1 - x) (1 - 4 x)), {x, 0, 20}], x] (* Michael De Vlieger, Mar 03 2017 *)

a(n)=2^(2*n+1)+1 \\ Charles R Greathouse IV, Sep 24 2015

G.f.: (3-6*x)/((1-x)*(1-4*x)).
a(n) = 3*A007583(n).
a(n) = 4*a(n-1) - 3. - Lekraj Beedassy, Apr 29 2005
a(n) = A099393(n+1) - 2*A099393(n). - Brad Clardy, Sep 01 2011
a(n) = 2^(2*n + 1)*a(-1-n) for all n in Z. - Michael Somos, Jan 11 2017
a(n) = A283070(n) - 1. - Peter M. Chema, Mar 02 2017
From Elmo R. Oliveira, Feb 22 2025: (Start)
E.g.f.: exp(x)*(2*exp(3*x) + 1).
a(n) = 5*a(n-1) - 4*a(n-2). (End)

A347834 An array A of the positive odd numbers, read by antidiagonals upwards, giving the present triangle T.

Original entry on oeis.org

1, 3, 5, 7, 13, 21, 9, 29, 53, 85, 11, 37, 117, 213, 341, 15, 45, 149, 469, 853, 1365, 17, 61, 181, 597, 1877, 3413, 5461, 19, 69, 245, 725, 2389, 7509, 13653, 21845, 23, 77, 277, 981, 2901, 9557, 30037, 54613, 87381, 25, 93, 309, 1109, 3925, 11605, 38229, 120149, 218453, 349525

Offset: 1

Wolfdieter Lang, Sep 20 2021

For the definition of this array A see the formula section.
The rows of A appear in a draft by Immmo O. Kerner in eqs. (1) and (2) as so-called horizontal sequences (horizontale Folgen). Thanks to Dr. A. Eckert for sending me this paper.
This array with entry A(k, n) becomes equal to the array T with T(n, k) given in A178415 by using a permutation of the rows, and changing the offset: A(k, n) = T(pe(k), n+1), with pe(3*(L+1)) = 4*(L+1), pe(1+3*L) = 1 + 2*L, pe(2+3*L) = 2*(1 + 2*L), for L >= 0. This permutation appears in A265667.
A proper sub-array is A238475(n, k) = A(1 + 3*(k-1), n-1), for k >= 1 and n >= 1.
In the directed Collatz tree with nodes labeled with only positive odd numbers (see A256598 for the paths), here called CTodd, the level L = 0 (on the top) has the node with label 1 as root. Because 1 -> 1 there is an arrow (a 1-cycle or loop) at the root. The level L = 1 consists of the nodes with labels A(1, n), for n >= 1, and each node is connected to 1 by a downwards directed arrow. The next levels for L >= 2 are obtained using the successor rule (used also by Kerner): S(u) = (4*u - 1)/3 if u == 1 (mod 3), (2*u - 1)/3 if u == 5 (mod 3), and there is no successor S(u) = empty if u = 3 (mod 6), that is, this node is a leaf.
However, each node with label u on level L >= 1, except a leaf, has as successors at level L + 1 not only the node with S(u) but all the nodes with labels A(S(u), n), for n >= 0.
In this way each node (also the root) of this CTodd has in-degree 1 and infinite out-degree (for L >= 2 there are infinitely many infinite outgoing arrows). All nodes with label A(k, n) with n >= 1, have the same precursor as the node A(k,0) in this tree for each k >= 1.
Except for the loop (1-cycle) for the root 1 there are no cycles in this directed tree CTodd.
That each number N = 5 + 8*K, for K >= 0 appears in array A for some column n >= 1 uniquely can be proved, using the fact of strictly increasing rows and columns, by showing that the columns n = 1, 2, ..., c contain all positive integers congruent to 5 modulo 8 except those of the positive congruence class A(1, c+1) modulo 2^(2*c+3) by induction on c. [added Dec 05 2021]
Row index k for numbers congruent to 5 modulo 8: Each number N = 5 + 8*K, for K >= 0, from A004770 is a member of row k of the array A starting with element A(k, 0) = (2*A065883(2 + 3*N) - 1)/3. For this surjective map see A347840. [simplified Dec 05 2021]
The Collatz conjecture can be reduced to the conjecture that in this rooted and directed tree CTodd each positive odd number appears as a label once, that is, all entries of the array A appear.

			The array A(k, n) begins:
k\n  0   1   2    3    4     5      6      7       8       9       10 ...
-------------------------------------------------------------------------
1:   1   5  21   85  341  1365   5461  21845   87381  349525  1398101
2:   3  13  53  213  853  3413  13653  54613  218453  873813  3495253
3:   7  29 117  469 1877  7509  30037 120149  480597 1922389  7689557
4:   9  37 149  597 2389  9557  38229 152917  611669 2446677  9786709
5:  11  45 181  725 2901 11605  46421 185685  742741 2970965 11883861
6:  15  61 245  981 3925 15701  62805 251221 1004885 4019541 16078165
7:  17  69 277 1109 4437 17749  70997 283989 1135957 4543829 18175317
8:  19  77 309 1237 4949 19797  79189 316757 1267029 5068117 20272469
9:  23  93 373 1493 5973 23893  95573 382293 1529173 6116693 24466773
10: 25 101 405 1621 6485 25941 103765 415061 1660245 6640981 26563925
...
--------------------------------------------------------------------
The triangle T(k, n) begins:
k\n  0  1   2    3    4     5     6      7      8      9 ...
------------------------------------------------------------
1:   1
2:   3  5
3:   7 13  21
4:   9 29  53   85
5:  11 37 117  213  341
6:  15 45 149  469 853   1365
7:  17 61 181  597 1877  3413  5461
8:  19 69 245  725 2389  7509 13653  21845
9:  23 77 277  981 2901  9557 30037  54613  87381
10: 25 93 309 1109 3925 11605 38229 120149 218453 349525
...
-------------------------------------------------------------
Row index k of array A, for entries 5 (mod 8).
213 = 5 + 8*26. K = 28 is even, (3*231+1)/16 = 40, A065883(40) = 10, hence A(k, 0) = N' = (10-1)/3 = 3, and k = 2. Moreover, n = log_4((3*213 + 1)/(3*A(2,0) + 1)) = log_4(64) = 3. 213 = A(2, 3).
85 = 5 + 8*10. K = 10 is even, (3*85 + 1)/16 = 16, A065883(16) = 1, N' = (1-1)/3 = 0 is even, hence A(k, 0) = 4*0 + 1 = 1, k = 1. 85 = A(1, 3).
61 = 5 + 8*7, K = 7 is odd, k = (7+1)/2 + ceiling((7+1)/4) = 6, and n = log_4((3*61 + 1)/(3*A(6,0) + 1)) = 1. 61 = A(6, 1).
----------------------------------------------------------------------------

Paolo Xausa, Table of n, a(n) for n = 1..11325 (first 150 antidiagonals, flattened).
Immo O. Kerner, Elementarer Lösungsansatz zum Collatz-Ulam-Problem CUP oder das "3a + 1" Problem, Version Nov 26 2000.
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Row sequences of the array A, also diagonal sequences of the triangle T: -A007583 (k=0), A002450(n+1), A072197, A072261(n+1), A206374(n+1), A072262(n+1), A072262(n+1), A072201(n+1), A330246(n+1), ...
Column sequences of the array A, also of the triangle T (shifted): A047529, A347836, A347837, ...
Cf. A004770, A007494, A016777, A065883, A047395, A047529, A178415, A238475, A256598, A265667, A319451, A347839, A347840.

# Seen as an array:
A := (n, k) -> ((3*(n + floor(n/3)) - 1)*4^(k+1) - 2)/6:
for n from 1 to 6 do seq(A(n, k), k = 0..9) od;
# Seen as a triangle:
T := (n, k) -> 2^(2*k + 1)*(floor((n - k)/3) - k + n - 1/3) - 1/3:
for n from 1 to 9 do seq(T(n, k), k = 0..n-1) od;
# Using row expansion:
gf_row := k -> (1 / (x - 1) - A047395(k)) / (4*x - 1):
for k from 1 to 10 do seq(coeff(series(gf_row(k), x, 11), x, n), n = 0..10) od;
# Peter Luschny, Oct 09 2021

A347834[k_, n_] := (4^n*(6*(Floor[k/3] + k) - 2) - 1)/3;
Table[A347834[k - n, n], {k, 10}, {n, 0, k - 1}] (* Paolo Xausa, Jun 26 2025 *)

Array A:
A(k, 0) = A047529(k) (the positive odd numbers {1, 3, 7} (mod 8));
A(k, n) = ((3* A(k, 0) + 1)*4^n - 1)/3, for k >= 1 and n >= 0.
Recurrence for rows k >= 1: A(k, n) = 4*A(k, n-1) + 1, for n >= 1, with A(k, 0) = 2*(k + floor(k/3)) - 1 = A047529(k).
Explicit form: A(k, n) = ((3*(k + floor(k/3)) - 1)*4^(n+1) - 2)/6, k >= 1, n >= 0. Here 3*(k + floor(k/3)) = A319451(k).
Hence A(k, n) = 5 + 8*(2*A(k, n-2)), for n >= 1, with A(k, 0) = 2*(k + floor(k/3)) - 1 = A047529(k), and 2*A(k, -1) = (A(k, 1) - 5)/8 = k - 1 + floor(k/3) (equals index n of A(k, 1) in the sequence (A004770(n+1))_{n >= 0}). A(k, -1) is half-integer if k = A007494(m) = m + ceiling(m/2), for m >= 1, and A(k, -1) = 2*K if k = 1 + 3*K = A016777(K), for K >= 0.
O.g.f.: expansion in z gives o.g.f.s for rows k, also for k = 0: -A007583; expansion in x gives o.g.f.s for columns n.
  G(z, x) = (2*(-1 + 3*z + 3*z^2 + 7*z^3)*(1-x) - (1-4*x)*(1-z^3)) / (3*(1-x)*(1-4*x)*(1-z)*(1-z^3)).
Triangle T:
T(k, n) = A(k - n, n), for k >= 1 and n = 0..k-1.
A(k, n) = [x^n] (1/(x - 1) - A047395(k)) / (4*x - 1). - Peter Luschny, Oct 09 2021

A178415 Array T(n,k) of odd Collatz preimages read by antidiagonals.

Original entry on oeis.org

1, 3, 5, 9, 13, 21, 7, 37, 53, 85, 17, 29, 149, 213, 341, 11, 69, 117, 597, 853, 1365, 25, 45, 277, 469, 2389, 3413, 5461, 15, 101, 181, 1109, 1877, 9557, 13653, 21845, 33, 61, 405, 725, 4437, 7509, 38229, 54613, 87381, 19, 133, 245, 1621, 2901, 17749, 30037

Offset: 1

T. D. Noe, May 28 2010

Every odd number occurs uniquely in this array. See A178414.

			Array T begins:
.    1    5   21    85   341   1365    5461   21845    87381   349525
.    3   13   53   213   853   3413   13653   54613   218453   873813
.    9   37  149   597  2389   9557   38229  152917   611669  2446677
.    7   29  117   469  1877   7509   30037  120149   480597  1922389
.   17   69  277  1109  4437  17749   70997  283989  1135957  4543829
.   11   45  181   725  2901  11605   46421  185685   742741  2970965
.   25  101  405  1621  6485  25941  103765  415061  1660245  6640981
.   15   61  245   981  3925  15701   62805  251221  1004885  4019541
.   33  133  533  2133  8533  34133  136533  546133  2184533  8738133
.   19   77  309  1237  4949  19797   79189  316757  1267029  5068117
- _L. Edson Jeffery_, Mar 11 2015
From _Bob Selcoe_, Apr 09 2015 (Start):
n=5, j=13: T(5,3) = 277 = (13*4^3 - 1)/3;
n=6, j=17: T(6,4) = 725 = (17*2^7 - 1)/3.
(End)

T. D. Noe, T(n,k) for n = 1..50, by antidiagonals
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Rows of array: -A007583(k-1) (n=0), A002450 (n=1), A072197(k-1) (n=2), A206374(n=3), A072261 (n=4), A323824 (n=5), A072262 (n=6), A330246 (n=7), A072201 (n=8), ...
Columns of array: A022998(n-1)/2 (k=0), A178414 (k=1), ...
Cf. A347834 (permuted rows of the array).

t[n_,1] := t[n,1] = If[OddQ[n],4n-3,2n-1]; t[n_,k_] := t[n,k] = 4*t[n,k-1]+1; Flatten[Table[t[n-i+1,i], {n,20}, {i,n}]]

From Bob Selcoe, Apr 09 2015 (Start):
T(n,k) = 4*T(n,k-1) + 1.
T(n,k) = T(1,k) + 2^(2k+1)*(n-1)/2 when n is odd;
T(n,k) = T(2,k) + 4^k*(n-2)/2 when n >= 2 and n is even. So equivalently:
T(n,k) = T(n-2,k) + 2^(2k+1) when n is odd; and
T(n,k) = T(n-2,k) + 4^k when n is even.
Let j be the n-th positive odd number coprime with 3. Then:
T(n,k) = (j*4^k - 1)/3 when j == 1 (mod 3); and
T(n,k) = (j*2^(2k-1) - 1)/3 when j == 2 (mod 3).
(End)
From Wolfdieter Lang, Sep 18 2021: (Start)
T(n, k) = ((3*n - 1)*4^k - 2)/6 if n is even, and ((3*n - 2)*4^k - 1)/3 if n is odd, for n >= 1 and  k >= 1. Also for n = 0: -A007583(k-1), with A007583(-1) = 1/2, and for k = 0: A022998(n-1)/2, with A022998(-1) = -1.
O.g.f. for array T (with row n = 0 and column k = 0; z for rows and x for columns): G(z, x) = (1/(2*(1-x)*(1-4*x)*(1-z^2)^2)) * ((2*x-4)*z^3 + (3-5*x)*z^2 + 2*x*z + 3*x - 1). (End)

A036991 Numbers k with the property that in the binary expansion of k, reading from right to left, the number of 0's never exceeds the number of 1's.

Original entry on oeis.org

0, 1, 3, 5, 7, 11, 13, 15, 19, 21, 23, 27, 29, 31, 39, 43, 45, 47, 51, 53, 55, 59, 61, 63, 71, 75, 77, 79, 83, 85, 87, 91, 93, 95, 103, 107, 109, 111, 115, 117, 119, 123, 125, 127, 143, 151, 155, 157, 159, 167, 171, 173, 175, 179, 181, 183, 187, 189, 191, 199, 203

Offset: 1

N. J. A. Sloane

List of binary words that correspond to a valid pairing of parentheses. - Joerg Arndt, Nov 27 2004
This sequence includes as subsequences A000225, A002450, A007583, A036994, A052940, A112627, A113836, A113841, A290114; and also A015521 (without 0), A083713 (without 0), A086224 (without 6), A182512 (without 0). - Gennady Eremin, Nov 27 2021 and Aug 26 2023
Partial differences are powers of 2 (cf. A367626, A367627). - Gennady Eremin, Dec 23 2021
This is the sequence A030101(A014486(n)), n >= 0, sorted into ascending order. See A014486 for more references, illustrations, etc., concerning Dyck paths and other associated structures enumerated by the Catalan numbers. - Antti Karttunen, Sep 25 2023
The terms in this sequence with a given length in base 2 are counted by A001405. For example, the number of terms of bit length k=5 (these are 19, 21, 23, 27, 29, and 31) is equal to A001405(k-1) = A001405(4) = 6. - Gennady Eremin, Nov 07 2023

			From _Joerg Arndt_, Dec 05 2021: (Start)
List of binary words with parentheses for those in the sequence (indicated by P). The binary words are scanned starting from the least significant bit, while the parentheses words are written left to right:
     Binary   Parentheses (if the value is in the sequence)
00:  ..... P  [empty string]
01:  ....1 P   ()
02:  ...1.
03:  ...11 P   (())
04:  ..1..
05:  ..1.1 P   ()()
06:  ..11.
07:  ..111 P   ((()))
08:  .1...
09:  .1..1
10:  .1.1.
11:  .1.11 P   (()())
12:  .11..
13:  .11.1 P   ()(())
14:  .111.
15:  .1111 P   (((())))
16:  1....
17:  1...1
18:  1..1.
19:  1..11 P   (())()
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..13496 (all terms < 2^16; first 1000 terms from Reinhard Zumkeller)
Joerg Arndt, Matters Computational (The Fxtbook), section 1.28, pp. 78-80.
Gennady Eremin, Dyck Numbers, IV. Nested patterns in OEIS A036991, arXiv:2306.10318, 2023. See pp. 1-2, 4, 7-11, 13-14.
Gennady Eremin, Partitioning the set of natural numbers into Mersenne trees and into arithmetic progressions; Natural Matrix and Linnik's constant, arXiv:2405.16143 [math.CO], 2024. See pp 2-5, 14.
Gennady Eremin, Infinite matrix of odd natural numbers. A bit about Sophie Germain prime numbers, arXiv:2501.17090 [math.GM], 2025. See pp. 3, 11.
Index entries for sequences related to binary expansion of n

Cf. A350577 (primes subsequence).
See also A014486, A030101, A036988, A036990, A036992. A036994 is a subset (requires the count of zeros to be strictly less than the count of 1's).
See also A030308, A000225, A002450, A007583, A350346, A367625, A367626 & A367627 (first differences).

a036991 n = a036991_list !! (n-1)
a036991_list = filter ((p 1) . a030308_row) [0..] where
   p     []    = True
   p ones (0:bs) = ones > 1 && p (ones - 1) bs
   p ones (1:bs) = p (ones + 1) bs
-- Reinhard Zumkeller, Jul 31 2013

q:= proc(n) local l, t, i; l:= Bits[Split](n); t:=0;
      for i to nops(l) do t:= t-1+2*l[i];
        if t<0 then return false fi
      od: true
    end:
select(q, [$0..300])[];  # Alois P. Heinz, Oct 09 2019

moreOnesRLQ[n_Integer] := Module[{digits, len, flag = True, iter = 1, ones = 0, zeros = 0}, digits = Reverse[IntegerDigits[n, 2]]; len = Length[digits]; While[flag && iter < len, If[digits[[iter]] == 1, ones++, zeros++]; flag = ones >= zeros; iter++]; flag]; Select[Range[0, 203], moreOnesRLQ] (* Alonso del Arte, Sep 21 2011 *)
Join[{0},Select[Range[210],Min[Accumulate[Reverse[IntegerDigits[#,2]]/.{0->-1}]]>-1&]] (* Harvey P. Dale, Apr 18 2014 *)

select( {is_A036991(n,c=1)=!n||!until(!n>>=1,(c-=(-1)^bittest(n,0))||return)}, [0..99]) \\ M. F. Hasler, Nov 26 2021

def ok(n):
    if n == 0: return True # by definition
    count = {"0": 0, "1": 0}
    for bit in bin(n)[:1:-1]:
        count[bit] += 1
        if count["0"] > count["1"]: return False
    return True
print([k for k in range(204) if ok(k)]) # Michael S. Branicky, Nov 25 2021

from itertools import count, islice
def A036991_gen(): # generator of terms
    yield 0
    for n in count(1):
        s = bin(n)[2:]
        c, l = 0, len(s)
        for i in range(l):
            c += int(s[l-i-1])
            if 2*c <= i:
                break
        else:
            yield n
A036991_list = list(islice(A036991_gen(),20)) # Chai Wah Wu, Dec 30 2021

If a(n) = A000225(k) for some k, then a(n+1) = a(n) + A060546(k). - Gennady Eremin, Nov 07 2023

More terms from Erich Friedman
Edited by N. J. A. Sloane, Sep 14 2008 at the suggestion of R. J. Mathar
Offset corrected and example adjusted accordingly by Reinhard Zumkeller, Jul 31 2013

A007302 Optimal cost function between two processors at distance n.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 3, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3

Offset: 0

Simon Plouffe

Also the number of nonzero digits in the symmetric signed digit expansion of n with q=2 (i.e., the representation of n in the (-1,0,1)2 number system). - _Ralf Stephan, Jun 30 2003
Volger (1985) proves that a(n) <= ceiling(log_2(3n/2) / 2) and uses a(n) to derive an upper bound on the length of the minimum addition-subtraction chain for n. - Steven G. Johnson (stevenj(AT)math.mit.edu), May 01 2007
Starting from 0, the smallest number of steps to reach n, where each step involves moving a power of 2 in either direction. - Dmitry Kamenetsky, Jul 04 2023

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche and Jeffrey Shallit, The Ring of k-regular Sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Alma D'Aniello, Aldo de Luca, and Alessandro De Luca, On Christoffel and standard words and their derivatives, arXiv:1602.03231 [cs.DM], 2016 (mentions this sequence).
Clemens Heuberger and Helmut Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.
Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016. See section "The nonadjacent form and its Hamming weight".
Gurmeet Singh Manku and Joe Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 4.
Aline Parreau, Michel Rigo, Eric Rowland, and Elise Vandomme, A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences, arXiv preprint arXiv:1405.3532 [cs.FL], 2014.
Yaniv Sadeh, Ori Rottenstreich, and Haim Kaplan, Codes for Load Balancing in TCAMs: Size Analysis, arXiv:2212.13256 [cs.NI], 2022.
Joe Sawada, A simple Gray code to list all minimal signed binary representations, SIAM Journal on Discrete Mathematics, Vol. 21 No. 1 (2007), 16-25.
Hugo Volger, Some results on addition/subtraction chains, Information Processing Letters, vol. 20, p. 155-160 (1985).
A. Weitzman, Transformation of parallel programs guided by micro-analysis, pp. 155-159 of Algorithms Seminars 1992-1993, ed. B. Salvy, Report #2130, INRIA, Rocquencourt, Dec. 1993.
Index to sequences related to the complexity of n

Cf. A005578, A057526.
Subtracting 1 gives A280737.
Cf. A007583 (indices of record highs).

import Data.Bits (xor)
a007302 n = a000120 $ xor n (3 * n) :: Integer
-- Reinhard Zumkeller, Jun 17 2012

a[n_] := Count[ BitXor[ b1 = IntegerDigits[n, 2]; b3 = IntegerDigits[3*n, 2]; PadLeft[b1, Length[b3]], b3], 1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 20 2014, after Ramasamy Chandramouli *)

ep(r,n)=local(t=n/2^(r+2));floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6)
a(n)=sum(r=0,log(3*n)\log(2)-1,!!ep(r,n))
for(n=1,100,print1(a(n)", "))
/* corrected by Charles R Greathouse IV, Jun 16 2012 */

a(n)=hammingweight(bitxor(n,3*n)) \\ Charles R Greathouse IV, Jan 03 2017

a(0) = 0; a(n) = 1 if n is a power of 2; a(n) = 1 + min { a(n-2^k), a(2^(k+1)-n) } if 2^k < n < 2^(k+1).
a(n) = 0 if n = 0, = 1 if n = 1, = a(n/2) if n > 1 and n even and = min(a(n-1), a(n+1))+1 if n > 1 and n odd. - David W. Wilson, Dec 28 2005
a(n) = hammingweight( XOR(n, 3*n) ). - Ramasamy Chandramouli, Aug 20 2010
A007302(n) = A000120(n) - sum (A213629(n,A136412(k))). - Reinhard Zumkeller, Jun 17 2012
a(0) = 0; a(2n) = a(n); a(4n-1) = a(n) + 1; a(4n+1) = a(n) + 1. - Nathan Fox, Mar 12 2013

A100706 Bisection of A002275.

Original entry on oeis.org

1, 111, 11111, 1111111, 111111111, 11111111111, 1111111111111, 111111111111111, 11111111111111111, 1111111111111111111, 111111111111111111111, 11111111111111111111111

Offset: 0

N. J. A. Sloane, Nov 19 2004

Also the binary representation of the n-th iteration of the elementary cellular automaton starting with a single ON (black) cell for Rules 151, 159, 183, 191, 215, 222, 223, 247, 254 and 255. - Robert Price, Feb 21 2016

The aerated sequence 1, 0, 111, 0, 11111, 0, 1111111, ... is a linear divisibility sequence of order 4. It is the case P1 = 0, P2 = -9^2, Q = -10 of the 3-parameter family of 4th-order linear divisibility sequences found by Williams and Guy. Cf. A007583, A095372 and A299960. - Peter Bala, Aug 28 2019

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume.
S. Wolfram, A New Kind of Science
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
Index entries for linear recurrences with constant coefficients, signature (101,-100).

Cf. A002275, A099814 (other bisection), A007583, A095372, A299960.

seq((10^(2*n+1) - 1)/9,n=0..15); # C. Ronaldo (aga_new_ac(AT)hotmail.com), Jan 19 2005

Table[(10^(2*n + 1) - 1)/9, {n, 0, 100}] (* Robert Price, Feb 21 2016 *)

a(n) = (10^(2*n + 1) - 1)/9; \\ Michel Marcus, Mar 12 2023

def A100706(n): return (10**((n<<1)+1)-1)//9 # Chai Wah Wu, Nov 04 2022

Numbers composed entirely of 2*n+1 concatenated 1's for n >= 0.
O.g.f.: (1+10*x)/((-1+x)*(-1+100*x)). - R. J. Mathar, Apr 03 2008
From Klaus Purath, Sep 23 2020: (Start)
a(n) = Sum_{i = 0..2*n} 10^i.
a(n) = 101*a(n-1) - 100*a(n-2).
a(n) = 110*10^(2*n-2) + a(n-1).
a(n) = 100*a(n-1) + 11.
a(n) = (a(n-1)^2 - 1210*10^(2*n-4))/a(n-2). (End)

More terms from C. Ronaldo (aga_new_ac(AT)hotmail.com), Jan 19 2005

cp's OEIS Frontend

A075677 Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A047849 a(n) = (4^n + 2)/3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

A072197 a(n) = 4*a(n-1) + 1 with a(0) = 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A000979 Wagstaff primes: primes of form (2^p + 1)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

A087289 a(n) = 2^(2*n+1) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A347834 An array A of the positive odd numbers, read by antidiagonals upwards, giving the present triangle T.

Views

Author

Keywords

Comments