Hugo van der Sanden - cp's OEIS frontend

A362706 Number of squares formed by first n vertices of the infinite-dimensional hypercube.

0, 0, 0, 1, 1, 2, 3, 6, 6, 7, 9, 13, 16, 21, 27, 36, 36, 37, 40, 45, 50, 57, 66, 78, 85, 94, 106, 121, 136, 154, 175, 200, 200, 201, 205, 211, 219, 229, 242, 258, 271, 286, 305, 327, 351, 378, 409, 444, 463, 484, 510, 539, 571, 606, 646, 690, 729, 771, 819

Offset: 1

Hugo van der Sanden, Jun 22 2023

nonn

We can take the coordinates of a vertex to represent a binary number, so we define the n-th point to have coordinates represented by the binary expansion of n-1.
Let d(m) = a(m+1) - a(m) be the shifted first differences of a(n), so that d(m) represents the additional squares introduced by the (m+1)-th vertex. Then d(0) = d(2^x) = 0; when m = 2^x + 2^y, x > y, d(m) = A115990(x - 1, x - y - 1); generally, d(m) = sum d(k) for all k formed by selecting two 1's from the binary expansion of m. Thus d(7) = d(3) + d(5) + d(6).
a(n) is a lower bound for an infinite-dimensional extension of A051602. Peter Munn notes that it is not an upper bound: for example, the vertices of a regular {k-1}-simplex duplicated at unit distance in any orthogonal direction gives T_k squares from 2k+2 points, which exceeds a(n) at 6, 10 and 12 points.

			The 6 points (0,0,0), (1,0,0), (0,1,0), (1,1,0), (0,0,1), (1,0,1) give the squares (0,0,0), (1,0,0), (0,1,0), (1,1,0) and (0,0,0), (1,0,0), (0,0,1), (1,0,1). So a(6) = 2.

Cf. A345340, A115990, A051602.

a(2^k) = A345340(k).

A355903 Variant of Stepping Stones problem: here the stone you place only needs to divide the sum of its 8 neighbors.

Original entry on oeis.org

1, 27, 41, 67

Offset: 1

N. J. A. Sloane, Sep 17 2022, based on emails from Skylark Xentha Murphy-Davies and Hugo van der Sanden

To find a(n), start by placing n stones labeled 1 on an infinite chessboard.
Set k=2. At step k, you must place a stone labeled k in a square where the sum of its neighbors is x*k for some x >= 1. That is, the sum of the neighbors must be an integral multiple of k.
If there is no way to do that, this game ends, and you win k-1 dollars. If you can do it, you increment k and repeat.
Then a(n) = maximum number of dollars you can win with optimal play for any initial placement of the n starting stones.
The sequence was proposed by Skylark Xentha Murphy-Davies on Sep 16 2022. She found lower bounds for a(2), a(3), and a(4). On Sep 17 2022, Hugo van der Sanden showed that her lower bound for a(2) was the correct value, and found the values of a(3) and a(4).
In the original version of the problem (see A337663) each stone that you place must equal the sum of its 8 neighbors.

			Illustration for a(2) = 27 (discovered by _Skylark Xentha Murphy-Davies_ and proved optimal by _Hugo van der Sanden_):
    .  .  .  .  .  .  .  .
    . 21 20  .  .  .  .  .
   23 13  9 18  .  .  .  .
    . 12  5  4  . 14 25  .
    . 27 10  1  3 11 26  .
    .  .  .  .  2  6  . 22
    .  .  . 19  .  1  7 15
    .  .  .  . 17 16  8  .
    .  .  .  .  .  . 24  .
    .  .  .  .  .  .  .  .

Skylark Xentha Murphy-Davies and Hugo van der Sanden, Illustration for a(2) = 27 (Discovered by Skylark Xentha Murphy-Davies and proved optimal by Hugo van der Sanden.) [There are two choices for the 27 stone, indicated by dashed lines. The 27 in the top left corner is not part of the arrangement.]
N. J. A. Sloane, Brady Haran and Pete McPartlan, Stones on an Infinite Chessboard, Numberphile video (2022).
Hugo van der Sanden, Maximal examples for a(2), a(3), a(4)

Cf. A337663.

A340630 Fill an n X n square with nonnegative integers so that all n^2 von Neumann neighborhoods have distinct sums; a(n) is smallest possible sum of the entries.

Original entry on oeis.org

0, 6, 9, 27, 63, 128, 237

Offset: 1

Hugo van der Sanden, Jan 13 2021

Also known: 405 <= a(8) <= 411; 650 <= a(9) <= 653; a(10) = 992; 1454 <= a(11) <= 1457; 2061 <= a(12) <= 2066.

Conjecture: a(n) = ceiling( (n^4 - n^2 + 14) / 10 ), matching the lower bound, for all n > n_0 for some constant n_0.

			For n = 3 we can construct a square grid such as { 0, 0, 0; 0, 1, 3; 1, 4, 0 } in which the elements sum to 9, and for which the respective sums of each element with its orthogonal neighbors gives the co-grid { 0, 1, 3; 2, 8, 4; 5, 6, 7 } all of whose values are distinct, so a(3) <= 9. There is no qualifying grid with a smaller sum (indeed, by the lower bound no smaller one is possible), so a(3) = 9.
Examples for each size:
n = 1
  0
n = 2
  0 1
  2 3
n = 3
  0 0 0
  0 1 3
  1 4 0
n = 4
  0 0 0 0
  0 1 3 7
  3 6 3 1
  0 2 0 1
n = 5
  0  0  0  0  0
  0  9  5 11  1
  1  5  1  3  0
  1  6  4  6  0
  0  1  6  3  0
n = 6 (Rob Pratt)
  0  0  0  0  0  0
  0 12 10  5 15  1
  1  2  3  4  7  0
  0  3  4  3  9  0
  2 17  5  5 14  0
  0  0  0  2  4  0
n = 7 (Rob Pratt)
  0  0  2  0  0  0  0
  0  4 15 20  8 20  1
  0 13  0  0  0  6  0
  1  8  5 14 10 16  0
  0  9  0  2  0 14  0
  2 11 23 10  3 17  1
  0  0  0  0  0  2  0
n = 10
  0  0  0  0  0  0  0  0  0  0
  0  4 11 20 29 31 22 14  6  1
  1 11  5  0  0  0  0  0 14  0
  0 20 11 25 24 27 29 16 23  0
  0 30  0 33  8 10  7  0 32  0
  0 33  0 31  0 19 20  1 36  0
  0 24  1 25 30 14 31  0 27  0
  0 15  2 13  0  0 11  0 18  0
  1  7 15 24 34 37 28 16 10  0
  0  1  1  0  0  0  0  0  3  0

/* Example for a(n)<1/10*n^4+48*n^3+1299/10*n^2+4*n.
  To get the explicit matrix solution call F(n);
  this also checks if the matrix is a good solution or not. */
c(x,y,n)={if(x>1&&x1&&y0&&x<=n&&y>0&&y<=n, S[i,j]+=A[x,y])); w[n*(i-1)+j]=S[i,j]));
  if(length(Set(w))Robert Gerbicz, Jan 15 2021

/* Return 0 if the matrix M is not a solution, else sum of elements, always > 0 except for M=(0). The 2nd arg specifies the neighborhoods, see below. */
score(M, N=vN(#M), U=[])={M=concat(Vec(M)); for(i=1,#N, #U<#(U=setunion(U,[vecsum(vecextract(M,N[i]))])) || return); vecsum(M)}
/* The function vN() below computes the list of von Neumann neighborhoods for each cell labeled 1..n^2. (For repeated calls of score(), this should be computed once, stored, and given as 2nd arg.) */
vN(n)=vector(n^2,i,[c|c<-[i,i-n,if(i%n!=1,i-1),if(i%n,i+1),if(i<=n^2-n,i+n)],c>0])
/* Brute force computation of a(n), not practicable for n>=4. Optional args: verbosity (show increasingly better solutions), neighborhoods, lower & upper bound for elements, target value (stop if found). */
{a(n, verbose=1, N=vN(n), o=0, L=n^2\2+(n==2), T=(n^4-n^2+23)\10+(31 && forvec(M=vector(#N,i,[o,if(i>n||n==2,min(i,L))]), my(s=score(M,N)); if(s && sM. F. Hasler, Jan 15 2021

Lower bound: a(n) >= ceiling( (n^4 - n^2 + 14) / 10 ) for n > 1.
Proof: letting S_c be the sum of the corner elements and S_e the sum of the non-corner edge elements, the sum over all the n^2 von Neumann neighborhoods for any minimal example is 5a(n) - S_e - 2S_c. However those n^2 contributions are required to be n^2 distinct nonnegative integers, which must sum to at least Sum_{0 .. n^2 - 1} i = n^2 (n^2 - 1) / 2. For n > 4, getting the von Neumann neighborhoods of the corner elements to have distinct sums requires edge or corner elements contributing to sums of at least { 0, 1, 2, 3 }. The edge pieces adjacent to the corner with 0 sum must additionally have their other adjacent edge differ by at least 1, so we have S_e + 2S_c >= 7, and hence a(n) >= ceiling((n^2*(n^2 - 1)/2 + 7) / 5) = ceiling( (n^4 - n^2 + 14) / 10 ) for n > 4. Values found show that it actually holds for n > 1.
a(n) < (1/10)*n^4 + 48*n^3 + (1299/10)*n^2 + 4*n, see the PARI program. - Robert Gerbicz, Jan 15 2021

a(5) confirmed minimal and a(6)-a(7) found by Rob Pratt

A323417 When a prime-based mapping reaches 0.

Original entry on oeis.org

3, 2, 1, 6, 3, 2

Offset: 0

Hugo van der Sanden, Aug 30 2019

Writing p_i for the i-th prime, A000040(i); let n_0 = n, and apply the mapping n_i = n_{i-1} + p_i (if p_i > n_{i-1}) else n_{i-1} - p_i. Then a(n) is the least k > 0 for which n_k = 0, or -1 if no such k exists.
In the traversal of n_i for a given n, if it reaches a local minimum after subtracting p_i, it will next reach a local minimum at p_j which will be close to 3p_i.
Conjecture: a(n) > 0 for all n.
For n in { 6 16 20 30 42 50 51 56 70 76 84 85 90 92 }, a(n) is unknown; in each case either a(n) = -1 or a(n) > 2 * 10^12. a(n) is known for all other n <= 100: see the A-file for details.

Nicholas Matteo, Known values for n in 0 .. 1000

A309222 is the trajectory of this mapping with n_0 = 6.

A283832 First differences of A280774.

Original entry on oeis.org

1, 2, 3, 4, 3, 10, 4, 3, 4, 4, 10, 6, 8, 3, 4, 17, 4, 4, 9, 17, 7, 4, 4, 4, 5, 4, 13, 4, 20, 12, 14, 44, 3, 4, 13, 11, 4, 10, 11, 8, 11, 4, 16, 4, 4, 9, 8, 4, 20, 15, 6, 7, 16, 4, 6, 4, 8, 21, 14, 4, 26, 4, 15, 6, 4, 6, 12, 28, 23, 20, 10, 10, 52, 12

Offset: 1

N. J. A. Sloane, Mar 22 2017, following a posting to the Sequence Fans Mailing List by Hugo van der Sanden

nonn

Let s(m) = A280864(m). The sequence gives the lengths of successive segments when A280864 is split after any term s(m) where every prime divisor of s(m) has already divided s(m-1). (Then s(m+1) is the smallest number not yet in A280864 which is relatively prime to s(m).)

See the link "Properties of A280864" in A280864 for more information.

N. J. A. Sloane, Table of n, a(n) for n = 1..25317

Cf. A280864, A280774.

A275580 Add square root of sum of terms.

Original entry on oeis.org

1, 2, 3, 5, 8, 12, 17, 23, 31, 41, 52, 65, 81, 99, 119, 142, 168, 197, 229, 264, 303, 346, 392, 442, 497, 556, 619, 687, 760, 838, 921, 1009, 1103, 1203, 1308, 1419, 1537, 1661, 1791, 1928, 2072, 2223, 2381, 2546, 2719, 2900, 3088

Offset: 0

Hugo van der Sanden, Aug 02 2016

a(0) = 1; a(n) = a(n-1) + floor(sqrt(Sum_{i=0..n-1} a(i))).

This appears to give asymptotically a(n) = n^3/36, sum of terms n^4/144, regardless of the starting value a(0).

			a(3) = a(2) + floor(sqrt(1 + 2)) = 2 + 1 = 3;
a(4) = a(3) + floor(sqrt(1 + 2 + 3)) = 3 + 2 = 5.

Robert Israel, Table of n, a(n) for n = 0..10000
Robert Israel, Formulas for A275580
Christian Krause, LODA
Index entries for linear recurrences with constant coefficients, signature (3,-4,5,-6,5,-4,3,-1).

G:= (x^4-x^3+x^2-x+1)/((x^5+x^3-x^2-1)*(x-1)^3):
S:= series(G,x,101):
seq(coeff(S,x,j),j=0..100); # Robert Israel, Aug 09 2016

a = {1}; Do[AppendTo[a, a[[k]] + Floor@ Sqrt@ Total@ a], {k, 46}]; a (* Michael De Vlieger, Aug 03 2016 *)

lista(nn) = {my(va = vector(nn)); va[1] = 1; for (n=2, nn, va[n] = va[n-1] + floor(sqrt(sum(k=1, n-1, va[k])));); va;} \\ Michel Marcus, Aug 02 2016

G.f.: (1-x+x^2-x^3+x^4)/((1-x)^3(1+x^2-x^3-x^5)). See link "Formulas for A275580". - Robert Israel, Aug 09 2016

a(n) = n + 1 + Sum_{i=0..n} floor((floor(i^2 / 3) + i) / 4); derived from corresponding LODA program (see link). - Hugo van der Sanden, Feb 24 2021

A260349 a(n) = min(k : A046067((k+1)/2) = n).

Original entry on oeis.org

1, 3, 7, 17, 55, 59, 19, 167, 31, 311, 289, 227, 351, 203, 379, 197, 103, 1253, 829, 335, 211, 353, 649, 437, 1921, 1853, 2869, 917, 361, 263, 283, 1637, 1213, 3353, 1519, 797, 241, 1691, 259, 1391, 2503, 1109, 3859, 1857

Offset: 0

Hugo van der Sanden, Jul 23 2015

nonn

a(n) is the first odd number k for which k * 2^i + 1 is prime when i = n but composite for all i: 0 <= i < n, or 0 if no such k exists. Thus it is the first k for which A046067((k+1)/2) = n, and therefore also the first k for which you need to test the primality of exactly n values to show that it is not a Sierpiński number.

Jaeschke shows that for each n>0, the set {k : A046067((k+1)/2) = n} is infinite. - Jeppe Stig Nielsen, Jul 06 2020

			7 * 2^i + 1 is composite for i < 2 (with values 8, 15) but prime for i = 2 (29); the smaller odd numbers 1, 3 and 5 each yield a prime for smaller i, so a(2) = 7.

Hugo van der Sanden, Table of n, a(n) for n = 0..3253
G. Jaeschke, On the Smallest k Such that All k*2^N + 1 are Composite, Mathematics of Computation, Vol. 40, No. 161 (Jan., 1983), pp. 381-384.

Cf. A046067, A076336, A260350.

a(n)=forstep(k=1,+oo,2,for(i=0,n-1,ispseudoprime(k<Jeppe Stig Nielsen, Jul 06 2020

A260350 Define g(k) = min(n: n >= 0, 2^n + k prime). Then a(n) = min(odd k: g(k) = n).

Original entry on oeis.org

1, 3, 7, 23, 31, 47, 199, 83, 61, 257, 139, 953, 991, 647, 1735, 383, 511, 1337, 1069, 713, 271, 1937, 3223, 5213, 751, 8477, 4339, 353, 1501, 287, 829, 1553, 2371, 1811, 11185, 3023, 7381, 7937, 6439, 1433, 13975, 2897, 4183

Offset: 0

Hugo van der Sanden, Jul 23 2015

nonn

Previous name: a(n) = min(k : A067760((k-1)/2)) = n.
a(n) is the first odd number k for which 2^m + k is the first prime value, as m ranges from 0 to n, or 0 if no such k exists. Thus it is the first k for which A067760((k-1)/2) = n, and therefore also the first k for which you need to test primality of exactly n values to show that it is not a dual Sierpiński number.
In the name, g(n) = A067760(n) except for n=1. - Michel Marcus, Apr 07 2018

			2^i + 7 is composite for i < 2 (with values 8, 9) but prime for i = 2 (11); the smaller odd numbers 1, 3 and 5 each yield a prime for smaller i, so a(2) = 7.

Hugo van der Sanden, Table of n, a(n) for n = 0..1087

Cf. A067760, A076336, A260349.

g(k) = {my(j=0); while (!isprime(2^j+k), j++); j;}
a(n) = {my(k = 1); while(g(k) != n, k+=2); k;} \\ Michel Marcus, Apr 07 2018

For n>=2, a(n) = (min(k : A067760((k-1)/2)) = n). - Michel Marcus, Apr 07 2018

New name from Hugo van der Sanden and Michel Marcus, Apr 07 2018

A254638 Cardinality of Image^inf({ 2 }) under repeated base-n zero-split doubling.

Original entry on oeis.org

2, 6, 2, 20, 13, 72, 3, 92, 42, 308, 34, 900, 178, 1739, 4, 3349, 443, 4523, 387, 14364, 1827, 18672, 234, 39426, 15882, 52664, 8858, 128253, 28346, 123087, 5, 259207, 87797, 363512, 44545, 671389, 182549, 1336282, 18049, 1289210, 634402, 2679419, 156629

Offset: 2

Hugo van der Sanden, Feb 03 2015

Define f_b(x) to be the set of base b numbers left after splitting 2x at its zero digits and Image_b(S) = union_{x in S}{ { x } union f_b(S) }, then a(n) = | Image_n^inf({ 2 }) |.

			a(8) = 3 since f_8(2) = { 4 }, f_8(4) = { 1 }, f_8(1) = { 2 } so Image_8^inf({ 2 }) = { 1, 2, 4 } and |{ 1, 2, 4 }| = 3.

Hugo van der Sanden, Table of n, a(n) for n = 2..62
Hugo van der Sanden, Perl and C implementations, Feb 03 2015

Cf. A254637, A113918.

A254637 Maximal element of Image^inf({ 2 }) under repeated base-n zero-split doubling.

Original entry on oeis.org

2, 16, 2, 192, 128, 32768, 4, 69632, 23552, 25722880, 425984, 717895680, 1051828224, 217079873536, 8, 2270641389568, 10603200512, 156423849771008, 950175531008, 25160124578398208, 385584983965696, 450589122059304960, 40722497536, 53279734579488838656

Offset: 2

Hugo van der Sanden, Feb 03 2015

Define f_b(x) to be the set of base b numbers left after splitting 2x at its zero digits and Image_b(S) = union_{x in S}{ { x } union f_b(S) }, then a(n) = max(Image_n^inf({ 2 }))

			a(8) = 4 since f_8(2) = { 4 }, f_8(4) = { 1 }, f_8(1) = { 2 } so Image_8^inf({ 2 }) = { 1, 2, 4 }.

Hugo van der Sanden, Table of n, a(n) for n = 2..62
Hugo van der Sanden, Perl and C implementations, Feb 03 2015

Cf A254638, A113917

cp's OEIS Frontend

User: Hugo van der Sanden

A362706 Number of squares formed by first n vertices of the infinite-dimensional hypercube.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A355903 Variant of Stepping Stones problem: here the stone you place only needs to divide the sum of its 8 neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A340630 Fill an n X n square with nonnegative integers so that all n^2 von Neumann neighborhoods have distinct sums; a(n) is smallest possible sum of the entries.

Views

Author

Keywords

Comments

Examples

Programs

PARI

PARI

Formula

Extensions

A323417 When a prime-based mapping reaches 0.

Views

Author

Keywords

Comments

Links

Crossrefs

A283832 First differences of A280774.

Views

Author

Keywords

Comments

Links

Crossrefs

A275580 Add square root of sum of terms.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

PARI

Formula

A260349 a(n) = min(k : A046067((k+1)/2) = n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A260350 Define g(k) = min(n: n >= 0, 2^n + k prime). Then a(n) = min(odd k: g(k) = n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A254638 Cardinality of Image^inf({ 2 }) under repeated base-n zero-split doubling.

Views

Author