A379757 a(n) = a(n-1) + 1 with two exceptions: if a(n-1) is prime, a(n) = a(n-2) + a(n-1), or if a(n-1) is a power, a(n) = a(n-1) / (root factor), with initial three terms are 0, 1, 2.

0, 1, 2, 3, 5, 8, 4, 2, 6, 7, 13, 20, 21, 22, 23, 45, 46, 47, 93, 94, 95, 96, 97, 193, 290, 291, 292, 293, 585, 586, 587, 1173, 1174, 1175, 1176, 1177, 1178, 1179, 1180, 1181, 2361, 2362, 2363, 2364, 2365, 2366, 2367, 2368, 2369, 2370, 2371, 4741, 4742, 4743

Offset: 1

Author

Bill McEachen, Jan 02 2025

Keywords

• nonn
• easy

Comments

The construction rules are very basic, but lead to somewhat surprising results. Terms that are perfect powers are extremely rare (only n=6,7 so far). Additionally, the sequence is nearly all composites. Comparing to A000045, eight early distinct terms are in common, but it is unclear when another intersection is seen.

Examples

			We know a(1)=0, a(2)=1, a(3)=2. Since a(3) is prime, a(4)=a(2)+a(3)=3. Since a(4) is prime, a(5)=a(3)+a(4)=5. Similarly, a(6)=a(4)+a(5)=8. Since a(6) is a perfect power, a(7) = a(6)/2 since 8=2^3. Since a(7)=4 is another perfect power, a(8)=4/2=2. Since a(8) is prime, a(9)=a(7)+a(8)=6. For clarity, if a(n-1) = r^k, then a(n) = a(n-1)/r.
		

Crossrefs

Cf. A000045, A001597, A089580.

Programs

Mathematica

a[n_] := a[n] = If[n < 4, n-1, If[PrimeQ[a[n-1]], a[n-1] + a[n-2], If[(g = GCD @@ FactorInteger[a[n-1]][[;; , 2]]) > 1, a[n-1]^(1 - 1/g), a[n-1] + 1]]]; Array[a, 54] (* Amiram Eldar, Apr 10 2025 *)

Formula

Conjecture: log(a(n)) ~ k*sqrt(n).