Nicholas Drozd - cp's OEIS frontend

A349896 Record values in A349876.

0, 9, 6144, 8850, 63294, 167460, 1471350, 17358894, 19273044, 90701559, 153178644, 189719685, 197747394, 2017743225, 6233637435, 59571334269, 86021383575, 156569713710, 2073505928019, 2889765691185, 17962980751950, 56300638961700, 277087084821075, 329363647943184

Offset: 1

Nicholas Drozd, Dec 04 2021

Cf. A349876.

f(n) = my(d=divrem(n, 3)); if (d[2], f(5*d[1]+d[2]+3), n); \\ A349876
lista(nn) = {my(r=0); for (n=1, nn, my(x = f(n)); if (x>r, print1(x, ", "); r=x););} \\ Michel Marcus, Dec 06 2021

A349877 a(n) is the number of times the map x -> A353314(x) needs to be applied to n to reach a multiple of 3, or -1 if the trajectory never reaches a multiple of 3.

Original entry on oeis.org

0, 2, 14, 0, 1, 13, 0, 4, 1, 0, 12, 3, 0, 1, 3, 0, 4, 1, 0, 11, 2, 0, 1, 2, 0, 2, 1, 0, 2, 3, 0, 1, 3, 0, 10, 1, 0, 4, 5, 0, 1, 7, 0, 3, 1, 0, 3, 2, 0, 1, 2, 0, 2, 1, 0, 2, 4, 0, 1, 9, 0, 3, 1, 0, 3, 4, 0, 1, 5, 0, 6, 1, 0, 4, 2, 0, 1, 2, 0, 2, 1, 0, 2, 7, 0, 1, 4, 0, 6, 1, 0, 6, 3, 0, 1, 3, 0, 5, 1, 0, 8, 2, 0

Offset: 0

Nicholas Drozd, Dec 03 2021

Equally, number of iterations of A353313 needed to reach a multiple of 3, or -1 if no multiple of 3 is ever reached. - Antti Karttunen, Apr 14 2022

			a(1) = 2 : 1 -> 4 -> 9 (as it takes two applications of A353314 to reach a multiple of three),
a(2) = 14 : 2 -> 5 -> 10 -> 19 -> 34 -> 59 -> 100 -> 169 -> 284 -> 475 -> 794 -> 1325 -> 2210 -> 3685 -> 6144
a(3) = 0 : 3 (as the starting point 3 is already a multiple of 3).
a(4) = 1 : 4 -> 9
a(7) = 4 : 7 -> 14 -> 25 -> 44 -> 75.

Antti Karttunen, Table of n, a(n) for n = 0..19683

Cf. A010872, A349876, A353311, A353313.

A353314(n) = { my(r=(n%3)); if(!r,n,((5*((n-r)/3)) + r + 3)); };
A349877(n) = { my(k=0); while(n%3, k++; n = A353314(n)); (k); }; \\ Antti Karttunen, Apr 14 2022

import itertools
def f(n):
    for i in itertools.count():
        quot, rem = divmod(n, 3)
        if rem == 0:
            return i
        n = (5 * quot) + rem + 3

From Antti Karttunen, Apr 14 2022: (Start)
If A010872(n) = 0 then a(n) = 0, otherwise a(n) = 1 + a(A353314(n)).
a(n) < A353311(n) for all n.
(End)

Definition corrected and more terms from Antti Karttunen, Apr 14 2022

A349876 If n is divisible by 3, a(n) = n; otherwise n = 3k + r with r in {1, 2} and a(n) = a(5k + r + 3). a(n) = -1 if no multiple of three will be ever reached by iterating A353314.

Original entry on oeis.org

0, 9, 6144, 3, 9, 6144, 6, 75, 15, 9, 6144, 60, 12, 24, 75, 15, 144, 30, 18, 6144, 60, 21, 39, 69, 24, 75, 45, 27, 84, 144, 30, 54, 159, 33, 6144, 60, 36, 309, 519, 39, 69, 1560, 42, 210, 75, 45, 225, 135, 48, 84, 144, 51, 150, 90, 54, 159, 450, 57, 99, 6144, 60, 294, 105, 63

Offset: 0

Nicholas Drozd, Dec 03 2021

It is not known if this function is total, that is, if a(n) is well-defined for all n (this is the reason for the escape clause in the definition).
This is a so-called "Collatz-like" function, because A353313 and A353314 have some similarity to the Collatz function A006370.
The sequence can be implemented with a Turing machine with 4 states and 2 colors.

			a(1) = a(3*0 + 1) = a(5*0 + 1 + 3) = a(4)
a(4) = a(3*1 + 1) = a(5*1 + 1 + 3) = a(9)
a(9) = 9
Trajectory of a(1): 4, 9
a(7) = a(3*2 + 1) = a(5*2 + 1 + 3) = a(14)
a(14) = a(3*4 + 2) = a(5*4 + 2 + 3) = a(25)
a(25) = a(3*8 + 1) = a(5*8 + 1 + 3) = a(44)
a(44) = a(3*14 + 2) = a(5*14 + 2 + 3) = a(75)
a(75) = 75
Trajectory of a(7): 14, 25, 44, 75
Trajectory of a(2): 5, 10, 19, 34, 59, 100, 169, 284, 475, 794, 1325, 2210, 3685, 6144.

Antti Karttunen, Table of n, a(n) for n = 0..19683
Nick Drozd, A Busy Beaver Champion Derived from Scratch.
Shawn Ligocki, Collatz-like behavior of Busy Beavers.
Pascal Michel, Busy Beaver competition and Collatz-like problems, Arch. Math. Logic (1993), 32:351-367.

Cf. A010872, A349877, A349896 (record values), A353313, A353314.

Cf. also A006370.

a[n_] := a[n] = Module[{qr = QuotientRemainder[n, 3]}, If[qr[[2]] == 0, n, a[5*qr[[1]] + qr[[2]] + 3]]]; Array[a, 64, 0] (* Amiram Eldar, Jan 04 2022 *)

a(n) = my(d=divrem(n, 3)); if (d[2], a(5*d[1]+d[2]+3), n); \\ Michel Marcus, Dec 05 2021

def a(n):
    while True:
        quot, rem = divmod(n, 3)
        if rem == 0:
            return n
        n = (5 * quot) + rem + 3

If A010872(n) = 0 [when n is a multiple of 3], a(n) = n, otherwise a(n) = a(A353314(n)). [Here one may also use A353313 instead of A353314] - Antti Karttunen, Apr 14 2022

Formal escape clause added to the definition by Antti Karttunen, Apr 14 2022

A337025 Number of n-state 2-symbol halt-free Turing machines.

Original entry on oeis.org

1, 16, 4096, 2985984, 4294967296, 10240000000000, 36520347436056576, 182059119829942534144, 1208925819614629174706176, 10314424798490535546171949056, 109951162777600000000000000000000, 1432052311740255546466984939315265536

Offset: 0

Nicholas Drozd, Aug 11 2020

A Turing machine is halt-free if none of its instructions lead to the halt state.
This sequence is strictly less than A052200(n) for all n > 0, since halt-free n-state machines are a strict subset of all n-state machines.
Solutions to the so-called "Beeping Busy Beaver" problem will almost certainly be halt-free programs.
For n > 1, a(n) is the absolute value of the determinant of a Hadamard matrix of size 4(n-1). This is apparent from the fact that HH^T = nI_n implies det(H)^2 = det(nI_n) = n^n, so det(H) = +- n^(n/2) and plugging in 4n yields a(n). - Nour Abouyoussef, Jun 25 2025

Scott Aaronson, The Busy Beaver Frontier.
Nick Drozd, Beeping Busy Beavers.

Cf. A052200.

[((4 * n) ** 2) ** n for n in range(12)]

a(n) = ((4*n)^2)^n.

A265755 a(n) = a(n-1) + a(n-2) if n is even and a(n) = a(n-3) + a(n-4) if n is odd, with a(0) = a(1) = a(2) = 0 and a(3) = 1.

Original entry on oeis.org

0, 0, 0, 1, 1, 0, 1, 2, 3, 1, 4, 5, 9, 5, 14, 14, 28, 19, 47, 42, 89, 66, 155, 131, 286, 221, 507, 417, 924, 728, 1652, 1341, 2993, 2380, 5373, 4334, 9707, 7753, 17460, 14041, 31501, 25213, 56714, 45542, 102256, 81927, 184183, 147798, 331981, 266110, 598091, 479779, 1077870, 864201, 1942071, 1557649

Offset: 0

Nicholas Drozd, Dec 15 2015

			a(8) = a(7) + a(6)
     = a(4) + a(3) + a(5) + a(4)
     = (a(3) + a(2)) + a(3) + (a(2) + a(1)) + (a(3) + a(2))
     = 1 + 1 + 0 + 1
     = 3

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,1,0,2,0,-1).

Interleaves A006053 and A052547, with an extra leading 0.

A187066 with even values and odd values swapped and an extra leading 0.

a[0] = a[1] = a[2] = 0; a[3] = 1; a[n_] := a[n] = If[EvenQ@ n, a[n - 1] + a[n - 2], a[n - 3] + a[n - 4]]; Table[a@ n, {n, 0, 55}] (* Michael De Vlieger, Dec 15 2015 *)
nxt[{n_,a_,b_,c_,d_}]:={n+1,b,c,d,If[OddQ[n],c+d,a+b]}; NestList[nxt,{1,0,0,0,1},60][[All,2]] (* or *) LinearRecurrence[{0,1,0,2,0,-1},{0,0,0,1,1,0},60] (* Harvey P. Dale, Nov 10 2017 *)

concat(vector(3), Vec(x^3*(1+x-x^2)/(1-x^2-2*x^4+x^6) + O(x^70))) \\ Colin Barker, Dec 16 2015

From Colin Barker, Dec 16 2015: (Start)
a(n) = a(n-2) + 2*a(n-4) - a(n-6) for n>5.
G.f.: x^3*(1+x-x^2) / (1-x^2-2*x^4+x^6).
(End)

More terms from Michael De Vlieger, Dec 15 2015

A265822 If n is 0, 1, or prime, a(n) = n; else a(n) = a(n-1) + a(n-2).

Original entry on oeis.org

0, 1, 2, 3, 5, 5, 10, 7, 17, 24, 41, 11, 52, 13, 65, 78, 143, 17, 160, 19, 179, 198, 377, 23, 400, 423, 823, 1246, 2069, 29, 2098, 31, 2129, 2160, 4289, 6449, 10738, 37, 10775, 10812, 21587, 41, 21628, 43, 21671, 21714, 43385, 47, 43432, 43479, 86911, 130390, 217301, 53, 217354, 217407, 434761

Offset: 0

Nicholas Drozd, Dec 15 2015

			a(9) = a(8) + a(7)
     = a(7) + a(6) + 7
     = a(5) + a(4) + 14
     = a(3) + a(2) + 19
     = 24

a[0] = 0; a[1] = 1; a[n_] := a[n] = If[PrimeQ@ n, n, a[n - 1] + a[n - 2]]; Table[a@ n, {n, 0, 56}] (* Michael De Vlieger, Dec 15 2015 *)

See the name.

More terms from Michael De Vlieger, Dec 15 2015

cp's OEIS Frontend

User: Nicholas Drozd

A349896 Record values in A349876.

Views

Author

Keywords

Crossrefs

Programs

PARI

A349877 a(n) is the number of times the map x -> A353314(x) needs to be applied to n to reach a multiple of 3, or -1 if the trajectory never reaches a multiple of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A349876 If n is divisible by 3, a(n) = n; otherwise n = 3k + r with r in {1, 2} and a(n) = a(5k + r + 3). a(n) = -1 if no multiple of three will be ever reached by iterating A353314.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A337025 Number of n-state 2-symbol halt-free Turing machines.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A265755 a(n) = a(n-1) + a(n-2) if n is even and a(n) = a(n-3) + a(n-4) if n is odd, with a(0) = a(1) = a(2) = 0 and a(3) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A265822 If n is 0, 1, or prime, a(n) = n; else a(n) = a(n-1) + a(n-2).

Views

Author

Keywords

Examples

Programs

Mathematica

Formula

Extensions