A344443 -id:A344443 - cp's OEIS frontend

A352957 Triangle read by rows: Row n is the lexicographically earliest strictly monotonic completely additive sequence of length n.

0, 0, 1, 0, 1, 2, 0, 2, 3, 4, 0, 2, 3, 4, 5, 0, 3, 5, 6, 7, 8, 0, 3, 5, 6, 7, 8, 9, 0, 4, 6, 8, 9, 10, 11, 12, 0, 5, 8, 10, 11, 13, 14, 15, 16, 0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 0, 5, 8, 10, 12, 13, 14, 15, 16, 17, 18, 0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25

Offset: 1

Peter Munn, Apr 11 2022

Each sequence consists of nonnegative integers indexed from 1.
Note in particular in the formula section, the lower bound, floor(n/k), for first differences between terms in a row. This follows (using the additive property) from the strict monotonicity of floor(n/k)+1 consecutive terms near the end of the row.
For any k, with increasing length n >= k, the first k terms of the sequences approach similarity with a real-valued logarithmic function defined on the integers. For example, the asymptote of T(n,3)/T(n,2) is log(3)/log(2), A020857.

			(For row 4.) A completely additive sequence requires T(4,1) = 0. Strict monotonicity requires T(4,4) > T(4,3) > T(4,2). So T(4,4) >= T(4,2) + 2. Using the additivity this becomes T(4,2) + T(4,2) >= T(4,2) + T(4,1) + 2. Subtracting T(4,2) and substituting 0 for T(4,1) we get T(4,2) >= 2. So from T(4,4) > T(4,3) > T(4,2), we see T(4,3) >= 3, T(4,4) >= 4. So row 4 = (0, 2, 3, 4) as it is strictly monotonic and completely additive and from the preceding arguments is seen to be the lexicographically earliest such.
Triangle starts:
0;
0, 1;
0, 1,  2;
0, 2,  3,  4;
0, 2,  3,  4,  5;
0, 3,  5,  6,  7,  8;
0, 3,  5,  6,  7,  8,  9;
0, 4,  6,  8,  9, 10, 11, 12;
0, 5,  8, 10, 11, 13, 14, 15, 16;
0, 5,  8, 10, 12, 13, 14, 15, 16, 17;
0, 5,  8, 10, 12, 13, 14, 15, 16, 17, 18;
0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25;
0, 7, 11, 14, 16, 18, 19, 21, 22, 23, 24, 25, 26;
0, 7, 11, 14, 16, 18, 20, 21, 22, 23, 24, 25, 26, 27;
0, 8, 13, 16, 19, 21, 23, 24, 26, 27, 28, 29, 30, 31, 32;
0, 9, 14, 18, 21, 23, 25, 27, 28, 30, 31, 32, 33, 34, 35, 36;

Peter Munn, Rows n = 1..141, flattened
Encyclopedia of Mathematics, Additive arithmetic function.
Peter Munn, PARI program

Cf. A020857.
Completely additive sequences, s, with primes p mapped to a function of s(p-1) and maybe s(p+1): A064097, A344443, A344444; and for functions of earlier terms, see A334200.
For completely additive sequences with primes p mapped to a function of p, see A001414.
For completely additive sequences with prime(k) mapped to a function of k, see A104244.
For completely additive sequences where some primes are mapped to 1, the rest to 0 (notably, some ruler functions) see the cross-references in A249344.

The definition specifies: T(n,j*k) = T(n,j) + T(n,k); for k > 1, T(n,k) > T(n,k-1).
T(n,1) = 0, otherwise T(n,k) >= T(n,k-1) + floor(n/k).
For prime p, T(p,p) = T(p-1,p-1) + 1, otherwise T(p,k) = T(p-1,k).
T(n,2) >= 2*floor(n/4) + floor(n/9).
T(n,3) >= ceiling( (3*T(n,2) + floor(n/9)) / 2).
T(11,k) = A344443(k).
For k <> 13, T(23,k) = A344444(k).

A344444 Completely additive with a(2) = 12, a(3) = 19; for prime p > 3, a(p) = ceiling((a(p-1) + a(p+1))/2).

Original entry on oeis.org

0, 12, 19, 24, 28, 31, 34, 36, 38, 40, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 55, 56, 57, 57, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63, 63, 64, 64, 65, 65, 66, 66, 66, 67, 67, 67, 68, 68, 68, 69, 69, 69, 70, 70, 70, 71, 71, 71, 72, 72, 72, 72, 73, 73, 73, 73, 74, 74

Offset: 1

Peter Munn, May 20 2021

Monotonic until a(143) = 87 > 86 = a(144).
The only infinite monotonic completely additive integer sequence is the all 0's sequence (cf. A000004). The challenge taken up here is to specify one that is monotonic for a modestly long number of terms, using a comparatively short prescriptive definition.
To start we specify values for a(2) and a(3) so that a(3)/a(2) approximates log(3)/log(2). 19/12 is a good approximation relative to the size of denominator. This reflects 2^19 = 524288 having a similar magnitude to 3^12 = 531441. Equivalently, we can say 3 is approximately the 19th power of the 12th root of 2. This approximation is used to construct musical scales. (See the Enevoldsen link, also A143800.) There is no better approximation with a denominator smaller than 29. [Revised by Peter Munn, Jun 14 2022]
To find a good specification to use for a(p) for larger primes, p, we are guided by knowing that if 2*a(n) < a(n-1) + a(n+1) then a completely additive sequence is not monotonic after a(n^2-1) because a(n^2) < a((n-1)*(n+1)) = a(n^2-1). Considering n = p, we see we want a(p) >= (a(p-1) + a(p+1))/2; but the same consideration for n = p-1 shows we don't want a(p) larger than necessary. These considerations lead towards the choice of "a(p) = ceiling((a(p-1) + a(p+1))/2)" for use in the definition.

			a(4) = a(2*2) = a(2) + a(2) from the definition of completely additive. So a(4) = 12 + 12 = 24. Similarly, a(6) = a(2*3) = a(2) + a(3) = 12 + 19 = 31.
5 is a prime number greater than 3, so a(5) = ceiling((a(5-1) + a(5+1))/2). Using the values a(4) = 24 and a(6) = 31 that we calculated earlier, we get a(5) = ceiling((24 + 31)/2) = ceiling(27.5) = 28.
The sequence is defined as completely additive, so a(1) = 0, the identity element for addition. (To see this, note that "completely additive" implies a(2) = a(2*1) = a(2)+a(1), and solve the equation for a(1).)

Encyclopedia of Mathematics, Additive arithmetic function
Keith Enevoldsen, Twelve-Tone Musical Scale
Index entries for sequences related to music

Equivalent sequence with a(2)=5, a(3)=8: A344443.
First 10 terms match A143800.
Cf. row 23 of A352957.
Cf. A000004, A020857, A060528, A061920.
For other completely additive sequences see the references in A104244.

a[1] = 0; a[n_] := a[n] = Plus @@ ((Last[#] * Which[First[#] == 2, 12, First[#] == 3, 19, First[#] > 3, Ceiling[(a[First[#] - 1] + a[First[#] + 1])/2]]) & /@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jun 27 2021 *)

a(n*k) = a(n) + a(k).

cp's OEIS Frontend

A352957 Triangle read by rows: Row n is the lexicographically earliest strictly monotonic completely additive sequence of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula