A199561 -id:A199561 - cp's OEIS frontend

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

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)

A207262 a(n) = 2^(4n - 2) + 1.

Original entry on oeis.org

5, 65, 1025, 16385, 262145, 4194305, 67108865, 1073741825, 17179869185, 274877906945, 4398046511105, 70368744177665, 1125899906842625, 18014398509481985, 288230376151711745, 4611686018427387905, 73786976294838206465, 1180591620717411303425, 18889465931478580854785, 302231454903657293676545

Offset: 1

Alonso del Arte, Feb 16 2012

With the exception of the first term, all these numbers are composite, and in fact are all multiples of 5. The other factors can be considerably larger than 5, as is the case with say, 2^158 + 1. These numbers can be factored as (2^(2n - 1) + 2^n + 1)(2^(2n - 1) - 2^n + 1). For example, 2^6 + 1 = 65 = (2^3 + 2^2 + 1)(2^3 - 2^2 + 1) = 13 * 5.
This formula was discovered by Leon-Francois-Antoine Aurifeuille in 1873. Wells (2005) remarks that knowledge of this formula would have saved Fortune Landry years of work he spent factoring 2^58 + 1.
Aurifeuille actually rediscovered a very special case of the identity 4x^4+1 = (2x^2-2x+1)(2x^2+2x+1), which Euler communicated to Goldbach in 1742. (The Fuss reference is in my book Seminumerical Algorithms, 3rd ed., p. 392; I had cited Aurifeuille in the 1st and 2nd editions.) - Don Knuth, Feb 09 2013
An Engel expansion of 4 to the base 16 as defined in A181565, with the associated series expansion 4 = 16/5 + 16^2/(5*65) + 16^3/(5*65*1025) + 16^4/(5*65*1025*16385) + .... Cf. A087289 and A199561. - Peter Bala, Oct 29 2013
Conjecture: Let m = 4n - 2. a(n) equals the sum of the m-th powers of the divisors of m divided by the sum of the m-th powers of the odd divisors of m. - Ivan N. Ianakiev, Jan 29 2020

David Wells, Prime Numbers: The Most Mysterious Figures in Math. Hoboken, New Jersey: John Wiley & Sons (2005) p. 15

Vincenzo Librandi, Table of n, a(n) for n = 1..200
FactorDB, Factorizations of 2^(4*n-2)+1
P. H. Fuss, Correspondance math. et physique, 1 (1843) p. 145.
Primenumbers Yahoo Group, Aurifeuille and factoring, search results.
Eric Weisstein's World of Mathematics, Aurifeuillean Factorization.
Yahoo Groups, Aurifeuille and factoring
Index entries for linear recurrences with constant coefficients, signature (17,-16).

Cf. A000051, A052539 (supersets). A016825. A087289, A199561.

2^(4*Range[20] - 2) + 1
LinearRecurrence[{17, -16}, {5, 65}, 50] (* Vincenzo Librandi, Mar 03 2012 *)

a(n)=4^(2*n-1)+1 \\ Charles R Greathouse IV, Oct 07 2015

a(n) = 4^(2n - 1) + 1.
G.f.: 5*x*(1-4*x)/((1-x)*(1-16*x)). - Bruno Berselli, Feb 17 2012
a(1) = 5, a(n) = 16*(a(n-1) - 1) + 1. - Arkadiusz Wesolowski, Feb 17 2012
a(n) = 5*A299960(n-1). - R. J. Mathar, Feb 28 2018
E.g.f.: exp(x) + (exp(16*x) - 5)/4. - Stefano Spezia, Jan 30 2020

A199560 a(n) = (3*9^n + 1)/2.

Original entry on oeis.org

2, 14, 122, 1094, 9842, 88574, 797162, 7174454, 64570082, 581130734, 5230176602, 47071589414, 423644304722, 3812798742494, 34315188682442, 308836698141974, 2779530283277762, 25015772549499854, 225141952945498682, 2026277576509488134, 18236498188585393202

Offset: 0

Vincenzo Librandi, Nov 08 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (10,-9).

Cf. A066443, A199561.

Magma
```
[(3*9^n+1)/2: n in [0..30]];
```

LinearRecurrence[{10,-9},{2,14},30] (* or *) NestList[9#-4&,2,30] (* Harvey P. Dale, May 30 2012 *)

a(n) = 2*A066443(n).
a(n) = 9*a(n-1) - 4.
a(n) = 10*a(n-1) - 9*a(n-2).
G.f.: 2*(1-3*x)/((1-x)*(1-9*x)).
From Elmo R. Oliveira, Sep 13 2024: (Start)
E.g.f.: exp(x)*(3*exp(8*x) + 1)/2.
a(n) = A199561(n)/2. (End)

A336913 Image of n under the 3^x+1 map, which is a variation of the 3x+1 (Collatz) map.

Original entry on oeis.org

4, 1, 28, 2, 244, 2, 2188, 3, 19684, 3, 177148, 3, 1594324, 3, 14348908, 4, 129140164, 4, 1162261468, 4, 10460353204, 4, 94143178828, 4, 847288609444, 4, 7625597484988, 4, 68630377364884, 4, 617673396283948, 5, 5559060566555524, 5, 50031545098999708, 5

Offset: 1

Robert C. Lyons, Aug 08 2020

nonn

It seems that all 3^x+1 trajectories reach 1; this has been verified up to 10^9. Once a 3^x+1 trajectory reaches 1, it repeats the following cycle: 1, 4, 2, 1, 4, 2, 1, ...

			For n = 5, a(5) = 3^5+1 = 244, because 5 is odd.
For n = 6, a(6) = floor(log_2(6)) = 2, because 6 is even.

Wikipedia, Collatz conjecture

Cf. A006370 (image of n under the 3x+1 map).
Cf. A336914 (gives number of steps to reach 1).
See also A199561.

from math import floor, log
def a(n): return 3**n + 1 if n % 2 else int(floor(log(n, 2)))
print([a(n) for n in range(1, 51)])

'''
Program that confirms that 3^x+1 trajectories end with 1.
We avoid the expensive 3^n+1 calculation based on the following:
- 3^n is not a power of two (for n >= 1).
- 3^n+1 is not a power of two (for n > 1) because of the Catalan Conjecture, which was proven in 2002.
- Thus, floor(log2(3^n+1)) == floor(log2(3^n)) == floor(n*log2(3)) for n > 1.
Thanks to Clark R. Lyons for this optimization.
'''
from math import floor, log
log2_of_3 = log(3, 2) # 16 digits after the decimal point.
max_n = 10**15 / 2    # Larger values multiplied by log2_of_3 may have rounding errors.
def check_trajectory(n):
    while n > 1:
        if n % 2 == 0:
            n = int(floor(log(n, 2)))
        else:
            if n > max_n:
                raise ValueError(str(n) + " is too large to be multiplied by log2_of_3")
            n = int(floor(n * log2_of_3))
n = 1
while n <= 1000000000:
    check_trajectory(n)
    n += 1

a(n) = floor(log_2(n)) if n is even, 3^n+1 if n is odd.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A207262 a(n) = 2^(4n - 2) + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A199560 a(n) = (3*9^n + 1)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A336913 Image of n under the 3^x+1 map, which is a variation of the 3x+1 (Collatz) map.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula