A372555 -id:A372555 - cp's OEIS frontend

A372557 Numbers k such that the least number of Jacobsthal numbers that add up to k, A372555(k), is less than the number needed with the greedy algorithm, A265745(k).

63, 84, 148, 169, 191, 212, 234, 255, 276, 297, 319, 340, 404, 425, 489, 510, 532, 553, 575, 596, 617, 638, 660, 681, 703, 724, 746, 767, 788, 809, 831, 852, 874, 895, 917, 937, 938, 959, 980, 1002, 1022, 1023, 1044, 1065, 1087, 1108, 1129, 1150, 1172, 1193, 1215, 1236, 1258, 1278, 1279, 1300, 1321, 1343, 1363, 1364, 1428

Offset: 1

Antti Karttunen, May 07 2024

nonn

			63 = 21+21+21 has A372555(63)=3 for its optimal, non-greedy solution, and A265745(63) = 5 for its greedy solution 63 = 43+11+5+3+1, therefore 63 is included in this sequence. (From _Yuriko Suwa_'s Jul 11 2021 comment in A265745.)
84 = 21+21+21+21 has A372555(84)=4 for its optimal, non-greedy solution, and A265745(84) = 6 for its greedy solution 84 = 43+21+11+5+3+1, therefore 84 is included in this sequence.
169 = 85+21+21+21+21 has A372555(169)=5 for its optimal, non-greedy solution, and A265745(169) = 7 for its greedy solution 169 = 85+43+21+11+5+3+1, therefore 169 is included in this sequence.

Antti Karttunen, Table of n, a(n) for n = 1..22785

Cf. A001045, A265745, A372555.

Cf. A372558 (subsequence).

\\ For A372555, use the program given under that entry.
A130249(n) = (#binary(3*n+1)-1);
A001045(n) = (2^n - (-1)^n) / 3;
A265745(n) = { my(s=0); while(n,s++; n -= A001045(A130249(n))); (s); };
isA372557(k) = (A372555(k)<A265745(k));

A372556 a(n) = largest number k <= A130249(n) for which A372555(n-A001045(k)) = A372555(n)-1, where A372555(n) is the least number of Jacobsthal numbers that add up to n.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, May 07 2024

nonn

An auxiliary sequence for computing A372555 with a mutually recursive algorithm.
Differs from A130249 for the first time at n=63, 84, 191, 212, 255, etc. See A372558.
Conjecture: For all n, either a(n) = A130249(n) or a(n) = A130249(n)-1. In other words, there is always a minimal solution (in number of summands) for representing n as a sum of Jacobsthal numbers that its largest summand is either A001045(A130249(n)) [same as obtained with a greedy algorithm A265745], or the next smaller Jacobsthal number. - Antti Karttunen, May 10 2024

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

Cf. A001045, A130249, A147612, A372556, A372558.

up_to = 87381; \\ = A001045(18).
A001045(n) = (2^n - (-1)^n) / 3;
A130249(n) = (#binary(3*n+1)-1);
A372555_or_556list(up_to_n,return_556_instead) = { my(v372555 = vector(up_to_n), v372556 = vector(up_to_n)); v372555[1] = 1; v372556[1] = 2; for(n=2,#v372556, my(m=-1,mk=-1,s=A130249(n)); if(A001045(s)==n, v372555[n] = 1; v372556[n] = s, forstep(k=s, 1, -1, my(c=v372555[n-A001045(k)]); if(m<0 || cA001045(mk)])); if(return_556_instead,v372556,v372555); };
v372556 = A372555_or_556list(up_to,1);
A372556(n) = if(!n,n,v372556[n]);

Scheme
```
;; Use the program given in A372555.
```

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

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

A372561 Array read by upward antidiagonals: A(n, k) = A265745(A372560(n, k)) for n > 1, k >= 1.

Original entry on oeis.org

3, 5, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10347, 6251, 2155, 1131, 619, 363, 235, 107, 43, 27, 11, 7, 5

Offset: 1

Antti Karttunen, May 08 2024

In general, it seems that for n>2, k>1, A(n, k) = A(n-1, k+1) = A(k, n), except on those two anomalous antidiagonals, first on the thirteenth antidiagonal, where for n=1..13, A(n,14-n) obtains values 5, 7, 11, 27, 43, 107, 235, 363, 619, 1131, 2155, 6251, 10347, and then on the 30th antidiagonal, where for n=1.., A(n,31-n) obtains values 5, 11, 15, 23, 39, 71, 135, 391, 647, 1671, 2695, 4743, 17031, 33415, 49799, 82567, 148103, 410247, etc. The corresponding antidiagonals in A372560 begin as:
  233, 933, 14933, 978670933, 64138178286933, 1183140560213014108063589658350933, ..., and:
  911, 58325, 933205, 238900565, 15656587449685, 67244531063362552157525, etc. I conjecture that for the former sequence of numbers x, from 933 onward, A372555(x) = 7, and for the latter sequence of numbers y, from 58325 onward, A372555(y) = 9, and that the array A372555(A372560(n, k)) is symmetric apart from its borders, i.e, that for n, k > 1, A372555(A372560(n, k)) = A372555(A372560(k, n)).

			Array begins:
n\k| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21
---+----------------------------------------------------------------
1  | 3, 5, 3, 3, 5, 3, 5, 5, 3, 5, 5, 5, 5, 3, 5, 3, 7, 5, 7, 5, 5,
2  | 5, 5, 5, 5, 3, 5, 5, 3, 5, 5, 5, 7, 5, 5, 5, 7, 5, 7, 7, 5, 5,
3  | 5, 5, 5, 3, 5, 5, 3, 5, 5, 5, 11, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7,
4  | 5, 5, 3, 5, 5, 3, 5, 5, 5, 27, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9,
5  | 5, 3, 5, 5, 3, 5, 5, 5, 43, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7,
6  | 3, 5, 5, 3, 5, 5, 5, 107, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7,
7  | 5, 5, 3, 5, 5, 5, 235, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7,
8  | 5, 3, 5, 5, 5, 363, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9,
9  | 3, 5, 5, 5, 619, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7,
10 | 5, 5, 5, 1131, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 1671,
11 | 5, 5, 2155, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 2695, 3,
12 | 5, 6251, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 4743, 3, 5,
13 | 10347, 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 17031, 3, 5, 3,
14 | 5, 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 33415, 3, 5, 3, 5,
15 | 5, 5, 7, 5, 7, 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 49799, 3, 5, 3, 5, 5,
etc.
From column 19 to column 41, the first 11 rows:
n\k|19 20 ........................................................... 40 41
---+-------------------------------------------------------------------------
1  | 7, 5, 5, 5, 7, 7, 5, 5, 5, 7, 7, 5,    3, 3, 3, 5, 5, 5, 5, 3, 3, 3, 1,
2  | 7, 5, 5, 7, 9, 7, 7, 7, 9, 7, 11,   3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1,
3  | 5, 5, 7, 9, 7, 7, 7, 9, 7, 15,   3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1,
4  | 5, 7, 9, 7, 7, 7, 9, 7, 23,   3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1,
5  | 7, 9, 7, 7, 7, 9, 7, 39,   3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1,
6  | 9, 7, 7, 7, 9, 7, 71,   3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1, 1,
7  | 7, 7, 7, 9, 7, 135,  3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1, 1, 1,
8  | 7, 7, 9, 7, 391,  3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1,
9  | 7, 9, 7, 647,  3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1,
10 | 9, 7, 1671, 3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
11 | 7, 2695, 3, 5, 3, 5, 5, 5, 5, 3, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

Cf. A265745, A371094, A372282, A372288, A372555, A372560.

\\ Needs also program from A372560.
up_to = 91;
A001045(n) = (2^n - (-1)^n) / 3;
A130249(n) = (#binary(3*n+1)-1);
A265745(n) = { my(s=0); while(n,s++; n -= A001045(A130249(n))); (s); };
A372561sq(n,k) = A265745(A372560sq(n,k));
A372561list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A372561sq((a-(col-1)),col))); (v); };
v372561 = A372561list(up_to);
A372561(n) = v372561[n];

A372558 Numbers k such that A130249(k) differs from A372556(k).

Original entry on oeis.org

63, 84, 191, 212, 255, 276, 297, 340, 703, 724, 767, 788, 809, 852, 937, 1022, 1023, 1044, 1065, 1108, 1129, 1150, 1193, 1278, 1363, 1364, 2751, 2772, 2815, 2836, 2857, 2900, 2985, 3070, 3071, 3092, 3113, 3156, 3177, 3198, 3241, 3326, 3411, 3412, 3497, 3582, 3667, 3752, 3753, 3838, 3923, 4008, 4093, 4094, 4095

Offset: 1

Antti Karttunen, May 07 2024

nonn

			From the terms of A372557 both 63 and 84 are included here, because the largest summand in their non-greedy solutions is different from the largest summand in their greedy solutions, while 169 is NOT included because the largest summand in both cases is 85. See examples in A372557.

Antti Karttunen, Table of n, a(n) for n = 1..24118

Cf. A001045, A130249, A372555, A372556.

Subsequence of A372557.

A130249(n) = (#binary(3*n+1)-1);
isA372558(k) = (A372556(k)!=A130249(k)); \\ Uses also the program from A372556.

cp's OEIS Frontend

A372557 Numbers k such that the least number of Jacobsthal numbers that add up to k, A372555(k), is less than the number needed with the greedy algorithm, A265745(k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A372556 a(n) = largest number k <= A130249(n) for which A372555(n-A001045(k)) = A372555(n)-1, where A372555(n) is the least number of Jacobsthal numbers that add up to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

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

A372561 Array read by upward antidiagonals: A(n, k) = A265745(A372560(n, k)) for n > 1, k >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A372558 Numbers k such that A130249(k) differs from A372556(k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI