A265744 -id:A265744 - cp's OEIS frontend

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

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

Antti Karttunen, Dec 17 2015

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

			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.

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

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.

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 *)

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

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

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

A352320 Pell-Niven numbers: numbers that are divisible by the sum of the digits in their minimal (or greedy) representation in terms of the Pell numbers (A317204).

Original entry on oeis.org

1, 2, 4, 5, 6, 9, 10, 12, 14, 15, 18, 20, 24, 28, 29, 30, 33, 34, 36, 39, 40, 42, 44, 48, 50, 58, 60, 63, 64, 68, 70, 72, 82, 84, 87, 88, 90, 92, 96, 110, 111, 112, 115, 116, 120, 125, 126, 135, 140, 141, 144, 155, 164, 165, 168, 169, 170, 174, 180, 183, 184, 186

Offset: 1

Amiram Eldar, Mar 12 2022

Numbers k such that A265744(k) | k.

All the positive Pell numbers (A000129) are terms.

			6 is a term since its minimal Pell representation, A317204(6) = 101, has A265744(6) = 2 1's and 6 is divisible by 2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000129, A265744, A317204.
Subsequences: A352321, A352322.
Similar sequences: A005349, A049445, A064150, A064438, A064481, A118363, A328208, A328212, A331085, A333426, A342726, A334308, A331728, A342426, A344341, A351714, A351719, A352089, A352107.

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; q[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]; Divisible[n, Plus @@ IntegerDigits[ Total[3^(s - 1)], 3]]]; Select[Range[200], q]

A352321 Numbers k such that k and k+1 are both Pell-Niven numbers (A352320).

Original entry on oeis.org

1, 4, 5, 9, 14, 28, 29, 33, 39, 63, 87, 110, 111, 115, 125, 140, 164, 168, 169, 183, 255, 275, 308, 338, 410, 444, 483, 507, 564, 579, 584, 704, 791, 984, 985, 999, 1004, 1024, 1025, 1115, 1134, 1154, 1164, 1211, 1265, 1308, 1323, 1351, 1395, 1415, 1424, 1491

Offset: 1

Amiram Eldar, Mar 12 2022

All the odd-indexed Pell numbers (A001653) are terms.

			4 is a term since 4 and 5 are both Pell-Niven numbers: the minimal Pell representation of 4, A317204(20) = 20, has the sum of digits 2+0 = 2 and 4 is divisible by 2, and the minimal Pell representation of 5, A317204(5) = 100, has the sum of digits 1+0+0 = 1 and 5 is divisible by 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000129, A265744, A317204.
Subsequence of A352320.
Subsequences: A001653, A352322.
Similar sequences: A330927, A328205, A328209, A328213, A330931, A331086, A333427, A334309, A331820, A342427, A344342, A351715, A351720, A352090, A352108.

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; q[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]; Divisible[n, Plus @@ IntegerDigits[ Total[3^(s - 1)], 3]]]; Select[Range[1500], q[#] && q[#+1] &]

A352322 Starts of runs of 3 consecutive Pell-Niven numbers (A352320).

Original entry on oeis.org

4, 28, 110, 168, 984, 1024, 3123, 3514, 5740, 6783, 6923, 8584, 12664, 16744, 18160, 19670, 23190, 23470, 24030, 34503, 34643, 36304, 40384, 45880, 47390, 50910, 51190, 51750, 57607, 61640, 68104, 73600, 78403, 78630, 78910, 79470, 86674, 89360, 95824, 101320

Offset: 1

Amiram Eldar, Mar 12 2022

Conjecture: There are no runs of 4 consecutive Pell-Niven numbers (checked up to 2*10^8).

			4 is a term since 4, 5 and 6 are all Pell-Niven numbers: the minimal Pell representation of 4, A317204(20) = 20, has the sum of digits 2+0 = 2 and 4 is divisible by 2, the minimal Pell representation of 5, A317204(5) = 100, has the sum of digits 1+0+0 = 1 and 5 is divisible by 1, and the minimal Pell representation of 6, A317204(6) = 101, has the sum of digits 1+0+1 = 2 and 6 is divisible by 2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000129, A265744, A317204.
A182190 \ {0} is a subsequence.
Subsequence of A352320 and A352321.
Similar sequences: A154701, A328206, A328210, A328214, A330932, A331087, A333428, A334310, A331822, A342428, A344343, A351716, A351721, A352091, A352109.

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; pellNivenQ[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]; Divisible[n, Plus @@ IntegerDigits[Total[3^(s - 1)], 3]]]; seq[count_, nConsec_] := Module[{pn = pellNivenQ /@ Range[nConsec], s = {}, c = 0, k = nConsec + 1}, While[c < count, If[And @@ pn, c++; AppendTo[s, k - nConsec]]; pn = Join[Rest[pn], {pellNivenQ[k]}]; k++]; s]; seq[30, 3]

A276328 Digit sum when n is expressed in greedy A001563-base (A276326).

Original entry on oeis.org

0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 5, 6, 7, 8, 6, 7, 1

Offset: 0

Antti Karttunen, Aug 30 2016

a(n) is the number of terms of A001563 needed to sum to n using the greedy algorithm.

This seems to give also the minimal number of terms of A001563 that sum to n (checked empirically up to n=3265920), but it would be nice to know for sure whether this holds for all n.

			For n=1, the largest term of A001563 <= 1 is A001563(1) = 1, thus a(1) = 1.
For n=2, the largest term of A001563 <= 2 is A001563(1) = 1, thus a(2) = 1 + a(2-1) = 2.
For n=18, the largest term of A001563 <= 18 is A001563(3) = 18, thus a(18) = 1.
For n=20, the largest term of A001563 <= 20 is A001563(3) = 18, thus a(20) = 1 + a(20-18) = 3.
For n=36, the largest term of A001563 <= 36 is A001563(3) = 18, thus a(36) = 1 + a(18) = 2.

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

Cf. A001563, A258199.
Cf. A000120, A276329, A276330, A276332, A276333, A276335.
Cf. A276091 (gives all n for which a(n) = A276337(n)).
Cf. also A007895, A034968, A265744, A265745 for similar sequences.

f[n_] := Block[{a = {{0, n}}}, Do[AppendTo[a, {First@ #, Last@ #} &@ QuotientRemainder[a[[-1, -1]], (# #!) &[# - i]]], {i, 0, # - 1}] &@NestWhile[# + 1 &, 0, (# #!) &[# + 1] <= n &]; Rest[a][[All, 1]]]; {0}~Join~Table[Total@ f@ n, {n, 120}] (* Michael De Vlieger, Aug 31 2016 *)

a(0) = 0; for n >= 1, a(n) = 1 + a(n-A258199(n)).
a(0) = 0; for n >= 1, a(n) = A276333(n) + a(A276335(n)).
Other identities and observations. For all n >= 0:
a(A276091(n)) = A000120(n).
a(n) >= A276337(n).
It also seems that a(n) <= A276332(n) for all n.

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

Antti Karttunen, Dec 16 2015

nonn

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).

			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.

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

Cf. A078510 (from its term a(7) onward gives also the positions of ones here).

Cf. also A007895, A053610, A265743, A265744, A265745.

A352340 a(n) is the sum of digits of n in the maximal Pell representation of n (A352339).

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 4, 2, 3, 3, 4, 5, 3, 4, 4, 5, 3, 4, 5, 3, 4, 4, 5, 6, 4, 5, 5, 6, 4, 5, 6, 4, 5, 5, 6, 7, 5, 6, 6, 7, 8, 4, 5, 5, 6, 4, 5, 6, 4, 5, 5, 6, 7, 5, 6, 6, 7, 5, 6, 7, 5, 6, 6, 7, 8, 6, 7, 7, 8, 9, 5, 6, 6, 7, 5, 6, 7, 5, 6, 6, 7, 8, 6, 7, 7, 8, 6

Offset: 0

Amiram Eldar, Mar 12 2022

Amiram Eldar, Table of n, a(n) for n = 0..10000
A. F. Horadam, Maximal representations of positive integers by Pell numbers, The Fibonacci Quarterly, Vol. 32, No. 3 (1994), pp. 240-244.

Cf. A000129, A007953, A352339.

Similar sequences: A053735, A007895, A112310, A265744, A278043, A352104.

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; pellp[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]; IntegerDigits[Total[3^(s - 1)], 3]]; a[n_] := Module[{v = pellp[n]}, nv = Length[v]; i = 1; While[i <= nv - 2, If[v[[i]] > 0 && v[[i + 1]] == 0 && v[[i + 2]] < 2, v[[i ;; i + 2]] += {-1, 2, 1}; If[i > 2, i -= 3]]; i++]; i = Position[v, _?(# > 0 &)]; If[i == {}, 0, Total[v[[i[[1, 1]] ;; -1]]]]]; Array[a, 100, 0]

a(n) = A007953(A352339(n)).

a(n) >= A265744(n).

A265743 a(n) = number of terms of A005187 needed to sum to n using the greedy algorithm.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 17 2015

nonn

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.

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

Cf. A005187, A055938.

Cf. also A000120, A007895, A053610, A265404, A265744, A265745.

Other identities. For all n >= 1:

a(A005187(n)) = 1 and a(A055938(n)) > 1.

A352328 Nonnegative numbers that are the sum of distinct Pell numbers (A000129).

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 8, 12, 13, 14, 15, 17, 18, 19, 20, 29, 30, 31, 32, 34, 35, 36, 37, 41, 42, 43, 44, 46, 47, 48, 49, 70, 71, 72, 73, 75, 76, 77, 78, 82, 83, 84, 85, 87, 88, 89, 90, 99, 100, 101, 102, 104, 105, 106, 107, 111, 112, 113, 114, 116, 117, 118

Offset: 0

Rémy Sigrist, Mar 12 2022

This sequence is the complement of A352323.
Although this is a list, it has offset 0 for mathematical reasons: indeed, so, the binary expansion of n encodes the positive Pell numbers summing to a(n).
Every nonnegative integer is the sum of two (not necessarily distinct) terms of this sequence.

			For n = 42:
- 42 = 2^5 + 2^3 + 2^1,
- so a(42) = A000129(5+1) + A000129(3+1) + A000129(1+1) = 70 + 12 + 2 = 84.

L. Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Pellian Representations, The Fibonacci Quarterly, Vol. 10, No. 5 (1972), pp. 449-488.
Index entries for sequences related to binary expansion of n

Cf. A000120, A000129, A265744, A352323.

With[{pell = LinearRecurrence[{2, 1}, {1, 2}, 7]}, Select[Union[Plus @@@ Subsets[pell]], # <= pell[[-1]] &]] (* Amiram Eldar, Mar 12 2022 *)

a(n) = { my (v=0, k); while (n, n-=2^k=valuation(n, 2); v+=([2, 1; 1, 0]^(k+1))[2, 1]); return (v) }

a(n) = Sum_{k >= 0} b_k * A000129(k+1) where Sum_{k >= 0} b_k * 2^k is the binary expansion of n.

A265744(a(n)) = A000120(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A352320 Pell-Niven numbers: numbers that are divisible by the sum of the digits in their minimal (or greedy) representation in terms of the Pell numbers (A317204).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A352321 Numbers k such that k and k+1 are both Pell-Niven numbers (A352320).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A352322 Starts of runs of 3 consecutive Pell-Niven numbers (A352320).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A276328 Digit sum when n is expressed in greedy A001563-base (A276326).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A352340 a(n) is the sum of digits of n in the maximal Pell representation of n (A352339).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A265743 a(n) = number of terms of A005187 needed to sum to n using the greedy algorithm.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula