A237442 -id:A237442 - cp's OEIS frontend

A277071 Numbers n for which A277070(n) does not equal A237442(n).

41, 43, 59, 86, 88, 91, 113, 118, 123, 135, 155, 172, 176, 177, 182, 185, 209, 215, 226, 236, 239, 248, 261, 267, 270, 273, 275, 279, 307, 310, 311, 337, 339, 344, 347, 352, 354, 364, 365, 367, 369, 370, 371, 377, 383, 405, 407, 418, 425, 427, 430, 452, 455, 465, 472, 473, 475, 478, 479, 496, 499

Offset: 1

Michael De Vlieger, Sep 27 2016

nonn

These are numbers n for which the greedy algorithm A276380(n) produces a partition of n with more than A237442(n) terms that are all unique and in A003586.
A276380(n) = A237442(n) if n is in A003586. There may be more than one partition of n that has terms that are unique and in A003586. The first n in a(n) with that quality is n = 88.
A277070(n)-A237442(n) = 1 at {41, 43, 59, 86, 88, 91, 113, 118, ...}
A277070(n)-A237442(n) = 2 at {279, 371, 558, 837, 1116, 1240, 1267, ...}
A277070(n)-A237442(n) = 3 at {2777, 5554, ...}

			41 is in the sequence because A276380(41) = {1,4,36}, thus A277070(41) = 3, but A237442(41) = 2. The partition of 41 with unique terms that are all in A003586 is {9,32}.
88 is in the sequence because A276380(88) = {1,6,81}, thus A277070(88) = 3, but A237442(41) = 2. There are 2 partitions of 88 with unique terms that are all in A003586: {16,72} and {24,64}.

V. Dimitrov, G. Jullien, R. Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press, 2012, pp. 35-39.

Michael De Vlieger, Table of n, a(n) for n = 1..3000

Cf. A003586, A237442, A276380, A277070.

f[n_] := Length@ DeleteCases[Append[Abs@ Differences@ #, Last@ #], k_ /; k == 0] &@ NestWhileList[# - SelectFirst[# - Range[0, # - 1], Module[{a = #, b = 6}, While[And[a != 1, ! CoprimeQ[a, b]], b = GCD[a, b]; a = a/b]; a == 1] &] &, n, # > 1 &]; g[n_] := Block[{p = Select[Range@ n, FactorInteger[#][[-1, 1]] < 4 &], k = 1}, While[{} == Quiet@ IntegerPartitions[n, {k}, p, 1], k++]; k]; Select[Range@ 500, f@ # != g@ # &] (* function g after Giovanni Resta at A237442 *)

A276380 Irregular triangle where row n contains terms k of the partition of n produced by greedy algorithm such that all elements are in A003586.

Original entry on oeis.org

1, 2, 3, 4, 1, 4, 6, 1, 6, 8, 9, 1, 9, 2, 9, 12, 1, 12, 2, 12, 3, 12, 16, 1, 16, 18, 1, 18, 2, 18, 3, 18, 4, 18, 1, 4, 18, 24, 1, 24, 2, 24, 27, 1, 27, 2, 27, 3, 27, 4, 27, 32, 1, 32, 2, 32, 3, 32, 36, 1, 36, 2, 36, 3, 36, 4, 36, 1, 4, 36, 6, 36, 1, 6, 36, 8, 36, 9, 36, 1, 9, 36, 2, 9, 36, 48, 1, 48

Offset: 1

Michael De Vlieger, Sep 25 2016

This sequence uses a greedy algorithm f(x) to find the largest number k <= n such that k is in A003586. The function is recursively applied to the result until it reaches 1. This is the algorithm described in the reference p. 36. This sequence presents the terms in order from least to greatest term.
The reference suggests the greedy algorithm is one way to render n in a "dual-base number system", essentially base (2,3) with bases 2 and 3 arranged orthogonally to produce a matrix of places with values that are the tensor product of prime power ranges of 2 and 3. Place values are signified by 0 or 1. Thus we can boil down the matrix to simply list the values of places harboring digit 1.
Row n = n for n that are in A003586.
The reference defines a "canonic" representation of n on page 33 as having the lowest number of terms. The greedy algorithm does not always render the canonic representation. a(41) = {1,4,36}, but {9,32} is the shortest possible partition of 41 such that all terms are in A003586.
The terms in row n differ from the canonic terms at n = 41, 43, 59, 86, 88, 91, 113, 118, 123, 135, 155, 172, 176, 177, 182, 185, 209, 215, 226, 236, 239, 248... (i.e., A277071).

			Triangle begins:
1
2
3
4
1,4
6
1,6
8
9
1,9
2,9
12
1,12
2,12
3,12
16
1,16
18
1,18
2,18
3,18
4,18
1,4,18
...

V. Dimitrov, G. Jullien, and R. Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press, 2012, pp. 35-39.

Michael De Vlieger, Table of n, a(n) for n = 1..11006 (Rows 1 <= n <= 3600)

Cf. A003586, A237442 (least number of 3-smooth numbers that add up to n), A277070 (row lengths), A277071, A347860, A348599.

Table[Reverse@ DeleteCases[Append[Abs@ Differences@ #, Last@ #], k_ /; k == 0] &@ NestWhileList[# - SelectFirst[# - Range[0, # - 1], Block[{m = #, n = 6}, While[And[m != 1, ! CoprimeQ[m, n]], n = GCD[m, n]; m = m/n]; m == 1] &] &, n, # > 1 &], {n, 49}]

from itertools import count, takewhile
N = 50
def B(p): return list(takewhile(lambda x: x<=N, (p**i for i in count(0))))
B23set = set(b*t for b in B(2) for t in B(3) if b*t <= N)
B23lst = sorted(B23set, reverse=True)
def row(n):
    if n in B23set: return [n]
    big = next(t for t in B23lst if t <= n)
    return row(n - big) + [big]
print([t for r in range(1, N) for t in row(r)]) # Michael S. Branicky, Sep 14 2022

A018899 Smallest positive integer not representable as the sum of at most n distinct numbers of form 2^a*3^b.

Original entry on oeis.org

1, 5, 23, 431, 18431, 3448733, 1441896119

Offset: 0

Vassil Dimitrov (vassil(AT)Engn.Uwindsor.Ca), Aug 15 1996

			a(2) = 23 because all smaller positive integers can be expressed as the sum of at most two numbers of the form 2^a * 3^b but not 23: 1=1, 2=2, 3=1+2, 4=1+3, 5=2+3, 6=2+4, 7=3+4, 8=2+6, 9=3+6, 10=4+6, 11=3+8, 12=4+8, 13=4+9, 14=6+8, 15=6+9, 16=4+12, 17=8+9, 18=6+12, 19=3+16, 20=8+12, 21=9+12, 22=6+16.

Valérie Berthé and Laurent Imbert, Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System, Discrete Mathematics and Theoretical Computer Science, vol. 11 (2009) no 1, pp. 153-172.
Valérie Berthé's Publications.
Daniel Krenn, Vorapong Suppakitpaisarn, and Stephan Wagner, Multi-Base Representations and their Minimal Hamming Weight, Numeration 2018 (2018): 24.
Mike Oakes, Posting to primenumbers list, Aug 30 2003.
Mark Underwood and others, The "twothree" numbers, digest of 10 messages in primenumbers Yahoo group, Aug 29 - Aug 30, 2003.

Cf. A003586, A172116, A237442.

With[{s = Sort@ Flatten@ Table[2^a * 3^b, {a, 0, Log2@ #}, {b, 0, Log[3, #/(2^a)]}] &[2^16]}, {1}~Join~Array[Block[{k = 1}, While[! FreeQ[#, k], k++]; k] &@ Union[Total /@ Permutations[s, #]] &, 3]] (* Michael De Vlieger, Sep 04 2018 *)

a(6) = 1441896119 found by Mike Oakes, Sep 07 2003

A323046 Numbers that are neither 3-smooth nor a sum of two 3-smooth numbers.

Original entry on oeis.org

23, 46, 47, 53, 61, 69, 71, 77, 79, 92, 94, 95, 101, 103, 106, 107, 115, 119, 121, 122, 125, 127, 133, 138, 139, 141, 142, 143, 149, 151, 154, 157, 158, 159, 161, 167, 169, 173, 175, 179, 181, 183, 184, 185, 187, 188, 190, 191, 197, 199, 202, 203, 205, 206, 207, 211, 212, 213, 214, 215, 221, 223, 227, 229, 230, 231, 233

Offset: 1

Carlos Alves, Jan 03 2019

nonn

			23 is not in A003586; also 22 (23-1), 21 (23-2), 20 (23-3), 19 (23-2*2), 17 (23-2*3), 15 (23-2*2*2), 14 (23-3*3), 11 (23-2*2*3), 7 (23-2*2*2*2), 5 (23-2*3*3) are not in A003586.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A003586, A237442, A323047, A323049, A323050. Subsequence of A081329.

N:= 1000: # to get all terms <= N
S:= {seq(seq(2^i*3^j,i=0..ilog2(N/3^j)),j=0..floor(log[3](N)))}:
sort(convert({$1..N} minus S minus map(t -> op(map(`+`, S,t)), S), list)); # Robert Israel, May 19 2019

A277070 Row length of A276380(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 2, 3, 1, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 3, 2, 3, 3, 1, 2, 2, 2, 2

Offset: 1

Michael De Vlieger, Sep 27 2016

nonn

a(n) represents the partition size generated by greedy algorithm at A276380(n) such that all parts k are unique and in A003586.
See A276380 for further comments about the greedy algorithm.
Row n = 1 for n that are in A003586.
A237442(n) represents the smallest possible partition size such that all k are distinct and in A003586. The reference defines the "canonic" representation of n in the "dual-base number system", i.e., base(2,3), essentially as those which have length A237442(n).
a(n) differs from A237442(n) at n = 41, 43, 59, 86, 88, 91, 113, 118, 123, 135, 155, 172, 176, 177, 182, 185, 209, 215, 226, 236, 239, 248, ... (i.e., A277071).

			a(n) Terms k in row n of A276380:
1    1
1    2
1    3
1    4
2    1,4
1    6
2    1,6
1    8
1    9
2    1,9
2    2,9
1    12
2    1,12
2    2,12
2    3,12
1    16
2    1,16
1    18
2    1,18
2    2,18
2    3,18
2    4,18
3    1,4,18
...
a(41) = 3 since A276380(41) = {1,4,36}, but {9,32} is the shortest possible partition of 41 such that all terms are distinct and in A003586.
a(88) = 3 since A276380(88) = {1,6,81}, but {16,72} and {24,64} are shorter and have A237442(88) = 2 terms.

V. Dimitrov, G. Jullien, and R. Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press, 2012, pp. 35-39.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A003586, A237442, A276380, A277071.

Table[Length@ DeleteCases[Append[Abs@ Differences@ #, Last@ #], k_ /; k == 0] &@ NestWhileList[# - SelectFirst[# - Range[0, # - 1], Block[{m = #, n = 6}, While[And[m != 1, ! CoprimeQ[m, n]], n = GCD[m, n]; m = m/n]; m == 1] &] &, n, # > 1 &], {n, 100}]

from itertools import count, takewhile
N = 100
def B(p): return list(takewhile(lambda x: x<=N, (p**i for i in count(0))))
B23set = set(b*t for b in B(2) for t in B(3) if b*t <= N)
B23lst = sorted(B23set, reverse=True)
def a(n):
    if n in B23set: return 1
    big = next(t for t in B23lst if t <= n)
    return a(n - big) + 1
print([a(n) for n in range(1, N+1)]) # Michael S. Branicky, Sep 14 2022

A347860 Irregular triangle T(n,k) where row n is the partition of n with the least number of 3-smooth parts such that the product of parts is minimal.

Original entry on oeis.org

1, 2, 3, 4, 4, 1, 6, 6, 1, 8, 9, 9, 1, 9, 2, 12, 12, 1, 12, 2, 12, 3, 16, 16, 1, 18, 18, 1, 18, 2, 18, 3, 18, 4, 18, 4, 1, 24, 24, 1, 24, 2, 27, 27, 1, 27, 2, 27, 3, 27, 4, 32, 32, 1, 32, 2, 32, 3, 36, 36, 1, 36, 2, 36, 3, 36, 4, 32, 9, 36, 6, 27, 16, 36, 8, 36, 9

Offset: 1

Michael De Vlieger, Feb 23 2022

Let k = 2^a * 3^b be a part such that n is the sum of at least one such k. Then we may represent k at (a,b) on a Cartesian grid. In Dimitrov, et al., these k are known as "digits" in a 2-dimensional number base system. Since these partitions have the least number of parts (digits) in order to represent n, in Dimitrov this is called a "canonic form" for n in base (2,3).
These numbers represent an extreme representation where the digits tend to be spread farthest apart in the plot described above.
Additionally, this canonic representation of n is often identical to the greedy representation of n shown by row n in A276380.

			Triangle begins:
   1;
   2;
   3;
   4;
   4, 1;   (product smaller than (3,2))
   6;
   6, 1;   (product smaller than (4,3))
   8;
   9;
   9, 1;   (product least of {(9,1), (8,2), (6,4)})
   9, 2;   (product smaller than (8,3))
  12;
  ...

Vassil Dimitrov, Graham Jullien, and Roberto Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press (2012), 35-39.

Michael De Vlieger, Table of n, a(n) for n = 1..10093 (rows n = 1..3600, flattened)
Michael De Vlieger, Plot of parts in row n at (T(n,k), n) for n = 1..256.
Michael De Vlieger, Comparison of row n of this sequence with row n of A276380 for n = 1..256, showing terms of this sequence in blue, and those of A276380 in red. Where these coincide, we plot in black.
Michael De Vlieger, Plot T(n,k) at (T(n,k), n) for n = 1..10000.
Michael De Vlieger, Annotated plot of T(n,k) and S(n,k) = A276380(n,k), n = 1..128, accentuating T(n,k) in blue and S(n,k) in red, otherwise in black and white where they coincide. S(n,k) is the result of a greedy algorithm described in Dimitrov, et al., i.e., more parts such that the row sum equals n.
Michael De Vlieger, Annotated plot of m = A348599(n,k) and m = T(n,k) at (m, n) for n = 1..64, showing m in row n of this sequence in red, m in row n of A347860 in blue, but in black if these coincide.

Cf. A003586, A237442, A276380.

nn = 45; ss = Union@ Flatten@ Table[2^a*3^b, {a, 0, Log2[nn]}, {b, 0, Log[3, nn/(2^a)]}]; Table[Block[{k = 1, w, t = TakeWhile[ss, # <= n &]}, While[{} == Set[w, IntegerPartitions[n, {k}, t]], k++]; MinimalBy[w, Times @@ # &][[1]]], {n, nn}] // Flatten

A237442(n) = length of row n.

A348599 Irregular triangle T(n,k) where row n is the partition of n with the least number of 3-smooth parts such that the product of parts is maximal.

Original entry on oeis.org

1, 2, 3, 4, 3, 2, 6, 4, 3, 8, 9, 6, 4, 8, 3, 12, 9, 4, 8, 6, 9, 6, 16, 9, 8, 18, 16, 3, 12, 8, 12, 9, 16, 6, 9, 8, 6, 24, 16, 9, 18, 8, 27, 16, 12, 27, 2, 18, 12, 27, 4, 32, 24, 9, 18, 16, 27, 8, 36, 36, 1, 32, 6, 27, 12, 24, 16, 32, 9, 24, 18, 27, 16, 32, 12, 27, 18

Offset: 1

Michael De Vlieger, Feb 23 2022

Let k = 2^a * 3^b be a part such that n is the sum of at least one such k. Then we may represent k at (a,b) on a Cartesian grid. In Dimitrov, et al., these k are known as "digits" in a 2-dimensional number base system. Since these partitions have the least number of parts (digits) in order to represent n, in Dimitrov this is called a "canonic form" for n in base (2,3).

These numbers represent an extreme representation where the digits tend to be placed close together.

			Triangle begins:
   1;
   2;
   3;
   4;
   3, 2;    (product larger than (4,1))
   6;
   4, 3;    (product larger than (6,1))
   8;
   9;
   6, 4;    (product greatest of {(9,1), (8,2), (6,4)})
   8, 3;    (product larger than (9,2))
  12;
  ...

Vassil Dimitrov, Graham Jullien, and Roberto Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press (2012), 35-39.

Michael De Vlieger, Table of n, a(n) for n = 1..10093 (rows n = 1..3600, flattened)
Michael De Vlieger, Plot of parts in row n at (T(n,k), n), for n = 1..256.
Michael De Vlieger, Plot T(n,k) at (T(n,k), n) for n = 1..10000.
Michael De Vlieger, Annotated plot of m = A347860(n,k) and m = T(n,k) at (m, n) for n = 1..64, showing m in row n of this sequence in blue, m in row n of A347860 in red, but in black if these coincide.

Cf. A003586, A237442, A276380.

nn = 45; ss = Union@ Flatten@ Table[2^a*3^b, {a, 0, Log2[nn]}, {b, 0, Log[3, nn/(2^a)]}]; Table[Block[{k = 1, w, t = TakeWhile[ss, # <= n &]}, While[{} == Set[w, IntegerPartitions[n, {k}, t]], k++]; MaximalBy[w, Times @@ # &][[1]]], {n, nn}] // Flatten

A237442(n) = length of row n.

A323047 Numbers that are not the sum of three (or fewer) 3-smooth numbers.

Original entry on oeis.org

431, 485, 509, 565, 637, 671, 719, 725, 727, 862, 887, 935, 941, 943, 959, 967, 970, 1130, 1151, 1175, 1199, 1205, 1274, 1293, 1319, 1342, 1367, 1373, 1391, 1415, 1421, 1423, 1438, 1439, 1445, 1447, 1450, 1453, 1454, 1455, 1481, 1527, 1535, 1559

Offset: 1

Carlos Alves, Jan 03 2019

nonn

Numbers below 431 may be written as a sum of three (or fewer) elements in A003586. These are the first exceptions.

Below 18431 every number can be written as a sum of 4 or fewer 3-smooth numbers, and below 3448733 every number can be written as a sum of 5 or fewer 3-smooth numbers (cf. sequence A018899).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A003586, A018899, A237442, A323046, A323048, A323049, A323050.

N:= 1000: # for all terms <= N
S:= {seq(seq(2^i*3^j,i=0..ilog2(N/3^j)),j=0..floor(log[3](N)))}:
S2:= select(`<=`,map(t -> op(map(`+`, S,t)), S),N):
S3:= select(`<=`,map(t -> op(map(`+`, S,t)), S2), N):
A:= {$1..N} minus S minus S2 minus S3:
sort(convert(A,list)); # Robert Israel, May 19 2019

f[n_] := Union@ Flatten@ Table[2^a * 3^b, {a, 0, Log2[n]}, {b, 0, Log[3, n/2^a]}];
b=Block[{nn = 2000, s}, s = f[nn]; {0, 1, 2}~Join~Select[Union@ Flatten@ Outer[Plus, s, s, s], # <= nn &]]; Complement[Range[2000], b]

A277045 Irregular triangle T(n,k) read by rows giving the number of partitions of length k such that all of the members of the partition are distinct and in A003586.

Original entry on oeis.org

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

Offset: 1

Michael De Vlieger, Sep 27 2016

If n is in A003586, then T(n,1) = 1, else T(n,1) = 0.
T(n,k) also is the number of ways of representing n involving k 1's in the base(2,3) or "dual-base number system" (i.e., base(2,3)).
The number of "canonic" representations of n in a dual-base number system as defined by the reference as having the lowest number of terms, appears in the first column of the triangle with a value greater than 0.
A237442(n) = the least k with a nonzero value.

			Triangle starts:
1
1
1,1
1,1
0,2
1,1,1
0,2,1
1,1,1
1,2,2
0,3,1,1
0,2,3
1,2,3,1
0,2,4,1
0,2,3,2
0,2,4,3
1,1,4,2,1
0,2,4,3
1,2,4,4,1
0,2,5,4,1
0,3,3,5,1
...
Row n = 10 has terms {0,3,1,1} because 10 is not in A003586 thus k = 1 has value 0. The partitions of 10 that have distinct members that are in A003586 are {{1,9},{2,8},{4,6},{1,3,6},{1,2,3,4}}, thus there are 3 partitions of length k = 2, 1 of length k = 3, and 1 with k = 4. A237442(10) = 2.

V. Dimitrov, G. Jullien, R. Muscedere, Multiple Number Base System Theory and Applications, 2nd ed., CRC Press, 2012, pp. 35-39.

Cf. A003586, A237442, A276380.

nn = 6^6; t = Sort@ Select[Flatten@ KroneckerProduct[2^Range[0, Ceiling@ Log2@ nn], 3^Range[0, Ceiling@ Log[3, nn]]], # <= nn &]; Table[BinCounts[#, {1, Max@ # + 1, 1}] &@ Map[Length, #] &@ Select[Subsets@ TakeWhile[t, # <= n &], Total@ # == n &], {n, 40}]

cp's OEIS Frontend

A277071 Numbers n for which A277070(n) does not equal A237442(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A276380 Irregular triangle where row n contains terms k of the partition of n produced by greedy algorithm such that all elements are in A003586.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

A018899 Smallest positive integer not representable as the sum of at most n distinct numbers of form 2^a*3^b.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A323046 Numbers that are neither 3-smooth nor a sum of two 3-smooth numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A277070 Row length of A276380(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

A347860 Irregular triangle T(n,k) where row n is the partition of n with the least number of 3-smooth parts such that the product of parts is minimal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A348599 Irregular triangle T(n,k) where row n is the partition of n with the least number of 3-smooth parts such that the product of parts is maximal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A323047 Numbers that are not the sum of three (or fewer) 3-smooth numbers.