cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A265745 a(n) is the number of Jacobsthal numbers (A001045) needed to sum to n using the greedy algorithm.

Original entry on oeis.org

0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 4, 3, 4, 5, 4, 5, 4, 5, 6, 5, 6, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 2
Offset: 0

Views

Author

Antti Karttunen, Dec 17 2015

Keywords

Comments

Sum of digits in "Jacobsthal greedy base", A265747.
It would be nice to know for sure whether this sequence gives also the least number of Jacobsthal numbers that add to n, i.e., that there cannot be even better nongreedy solutions.
The integer 63=21+21+21 has 3 for its 'non-greedy' solution, and a(63) = 5 for its greedy solution 63=43+11+5+3+1. - Yuriko Suwa, Jul 11 2021
Positions where a(n) is different from A372555(n) are n=63, 84, 148, 169, 191, 212, 234, 255, etc. See A372557. - Antti Karttunen, May 07 2024

Examples

			a(0) = 0, because no numbers are needed to form an empty sum, which is zero.
For n=1 we need just A001045(2) = 1, thus a(1) = 1.
For n=2 we need A001045(2) + A001045(2) = 1 + 1, thus a(2) = 2.
For n=4 we need A001045(3) + A001045(2) = 3 + 1, thus a(4) = 2.
For n=6 we form the greedy sum as A001045(4) + A001045(2) = 5 + 1, thus a(6) = 2. Alternatively, we could form the sum as A001045(3) + A001045(3) = 3 + 3, but the number of summands in that case is no less.
For n=7 we need A001045(4) + A001045(2) + A001045(2) = 5 + 1 + 1, thus a(7) = 3.
For n=8 we need A001045(4) + A001045(3) = 5 + 3, thus a(8) = 2.
For n=10 we need A001045(4) + A001045(4) = 5 + 5, thus a(10) = 2.

Links

Crossrefs

Cf. A001045, A130249, A197911, A003158, A265746, A265747, A364377, A364379, A364380, A372288, A372555, A372557.
Cf. A054111 (apparently the positions of the first occurrence of each n > 0).
Cf. also A007895, A014420, A053610, A265404, A265743, A265744.

Programs

  • Mathematica
    jacob[n_] := (2^n - (-1)^n)/3; maxInd[n_] := Floor[Log2[3*n + 1]]; A265745[n_] := A265745[n] = 1 + A265745[n - jacob[maxInd[n]]]; A265745[0] = 0; Array[A265745, 100, 0] (* Amiram Eldar, Jul 21 2023 *)
  • PARI
    A130249(n) = floor(log(3*n + 1)/log(2));
A001045(n) = (2^n - (-1)^n) / 3;
A265745(n) = {if(n == 0, 0, my(d = n - A001045(A130249(n))); if(d == 0, 1, 1 + A265745(d)));} \\ Amiram Eldar, Jul 21 2023
  • Python
    def greedyJ(n): n1 = (3*n+1).bit_length() - 1; return (2**n1 - (-1)**n1)//3
def a(n): return 0 if n == 0 else 1 + a(n - greedyJ(n))
print([a(n) for n in range(107)]) # Michael S. Branicky, Jul 11 2021

Formula

a(0) = 0; for n >= 1, a(n) = 1 + a(n - A001045(A130249(n))). [This formula uses a simple greedy algorithm.]

A265744 a(n) is the number of Pell numbers (A000129) needed to sum to n using the greedy algorithm (A317204).

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 3
Offset: 0

Views

Author

Antti Karttunen, Dec 17 2015

Keywords

Comments

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.
It would be nice to know for sure whether this sequence also gives the least number of Pell numbers that add to n, i.e., that there cannot be even better nongreedy solutions.

References

  • A. F. Horadam, Zeckendorf representations of positive and negative integers by Pell numbers, Applications of Fibonacci Numbers, Springer, Dordrecht, 1993, pp. 305-316.

Links

Crossrefs

Cf. A000129, A007953, A317204.
Cf. also A014420, A053610, A265404, A265743, A265745.
Similar sequences: A007895, A116543, A278043.

Programs

  • Mathematica
    pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; a[n_] := Module[{s = {}, m = n, k}, While[m > 0, k = 1; While[pell[k] <= m, k++]; k--; AppendTo[s, k]; m -= pell[k]; k = 1]; Plus @@ IntegerDigits[Total[3^(s - 1)], 3]]; Array[a, 100, 0] (* Amiram Eldar, Mar 12 2022 *)

Formula

a(n) = A007953(A317204(n)). - Amiram Eldar, Mar 12 2022

A265404 a(n) = number of Spironacci numbers (A078510) needed to sum to n using the greedy algorithm.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2
Offset: 0

Views

Author

Antti Karttunen, Dec 16 2015

Keywords

Comments

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.
First 2 occurs as a(17), first 3 at a(234), first 4 at a(3266).

Examples

			For n=17, the largest Spironacci number <= 17 is 16 (= A078510(22)). 17 - 16 = 1, which is A078510(1), thus 17 = A078510(22) + A078510(1), requiring only two such numbers for its sum, thus a(17) = 2.
For n=234, the largest Spironacci number <= 234 is 217 (= A078510(45)). 234-217 = 17 (whose decomposition is shown above), so 234 = A078510(45) + A078510(22) + A078510(1), thus a(234) = 3.

Links

Crossrefs

Cf. A078510 (from its term a(7) onward gives also the positions of ones here).
Cf. also A007895, A053610, A265743, A265744, A265745.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.