A163361 -id:A163361 - cp's OEIS frontend

A163357 Hilbert curve in N X N grid, starting rightwards from the top-left corner, listed by descending antidiagonals.

0, 1, 3, 14, 2, 4, 15, 13, 7, 5, 16, 12, 8, 6, 58, 19, 17, 11, 9, 57, 59, 20, 18, 30, 10, 54, 56, 60, 21, 23, 29, 31, 53, 55, 61, 63, 234, 22, 24, 28, 32, 52, 50, 62, 64, 235, 233, 25, 27, 35, 33, 51, 49, 67, 65, 236, 232, 230, 26, 36, 34, 46, 48, 68, 66, 78, 239, 237, 231

Offset: 0

Antti Karttunen, Jul 29 2009

			The top left 8 X 8 corner of the array shows how this surjective self-avoiding walk begins (connect the terms in numerical order, 0-1-2-3-...):
   0  1 14 15 16 19 20 21
   3  2 13 12 17 18 23 22
   4  7  8 11 30 29 24 25
   5  6  9 10 31 28 27 26
  58 57 54 53 32 35 36 37
  59 56 55 52 33 34 39 38
  60 61 50 51 46 45 40 41
  63 62 49 48 47 44 43 42

A. Karttunen, Table of n, a(n) for n = 0..32895
Jörg Arndt, Plane-filling curves on all uniform grids, arXiv:1607.02433v1 [math.CO], July 11, 2016.
Herman Haverkort, Recursive tilings and space-filling curves
Herman Haverkort, The Sound of Space-Filling Curves, Proc. Bridges 2017, pp. 399-402.
Eric Weisstein's World of Mathematics, Hilbert curve
Wikipedia, Self-avoiding walk
Wikipedia, Space-filling curve
Index entries for sequences that are permutations of the nonnegative integers

Transpose: A163359. Inverse: A163358. One-based version: A163361. Row sums: A163365. Row 0: A163482. Column 0: A163483. Central diagonal: A062880. See also A163334 & A163336 for the Peano curve.

b[{n_, k_}, {m_}] := (A[k, n] = m-1);
MapIndexed[b, List @@ HilbertCurve[4][[1]]];
Table[A[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Mar 07 2021 *)

a(n) = A163355(A054238(n)).

Links to further derived sequences added by Antti Karttunen, Sep 21 2009

A326409 Minesweeper sequence of positive integers arranged on a 2D grid along Hamiltonian path.

Original entry on oeis.org

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

Offset: 1

Witold Tatkiewicz, Oct 07 2019

Place positive integers on a 2D grid starting with 1 in the top left corner and continue along Hamiltonian path A163361 or A163363.
Replace each prime with -1 and each nonprime by the number of primes in adjacent grid cells around it.
n is replaced by a(n).
This sequence treats prime numbers as "mines" and fills gaps according to rules of the classic Minesweeper game.
a(n) < 5.
Set of n such that a(n) = 4 is unbounded (conjectured).

			Consider positive integers distributed onto the plane along an increasing Hamiltonian path (in this case it starts downwards):
.
   1   4---5---6  59--60--61  64--...
   |   |       |   |       |   |
   2---3   8---7  58--57  62--63
           |           |
  15--14   9--10  55--56  51--50
   |   |       |   |       |   |
  16  13--12--11  54--53--52  49
   |                           |
  17--18  31--32--33--34  47--48
       |   |           |   |
  20--19  30--29  36--35  46--45
   |           |   |           |
  21  24--25  28  37  40--41  44
   |   |   |   |   |   |   |   |
  22--23  26--27  38--39  42--43
.
1 is not prime and in adjacent grid cells there are 2 primes: 2 and 3. Therefore a(1) = 2.
2 is prime, therefore a(2) = -1.
8 is not prime and in adjacent grid cells there are 3 primes: 5, 3 and 7. Therefore a(8) = 3.
Replacing n with a(n) in the plane described above, and using "." for a(n) = 0 and "*" for negative a(n), we produce a graph resembling Minesweeper, where the mines are situated at prime n:
  2   3---*---3   *---2---*   1 ...
  |   |       |   |       |   |
  *---*   3---*   2---2   1---1
          |           |
  3---3   4---2   3---1   1---.
  |   |       |   |       |   |
  2   *---3---*   2---*---2   1
  |                           |
  *---4   *---3---3---2   *---1
      |   |           |   |
  2---*   3---*   2---3   2---2
  |           |   |           |
  2   2---3   2   *   2---*   2
  |   |   |   |   |   |   |   |
  1---*   1---1   1---2   2---*
In order to produce the sequence, the graph is read along its original mapping.

Alexander Bogomolny, Plane Filling Curves: Hilbert's & Moore's, Cut the Knot.org, retrieved October 2019.
Eric Weisstein's World of Mathematics, Hilbert Curve.
Wikipedia, Hilbert Curve.
Wikipedia, Minesweeper game.

Cf. A163361 (plane mapping), A163363 (alternative plane mapping).

Different arrangements of integers: A326405 (antidiagonals), A326406 (triangle maze), A326407 (square mapping), A326408 (square maze), A326410 (Ulam's spiral).

Block[{nn = 4, s, t, u}, s = ConstantArray[0, {2^#, 2^#}] &[nn + 1]; t = First[HilbertCurve@ # /. Line -> List] &[nn + 1] &[nn + 1]; s = ArrayPad[ReplacePart[s, Array[{1, 1} + t[[#]] -> # &, 2^(2 (nn + 1))]], {{1, 0}, {1, 0}}]; u = Table[If[PrimeQ@ m, -1, Count[#, _?PrimeQ] &@ Union@ Map[s[[#1, #2]] & @@ # &, Join @@ Array[FirstPosition[s, m] + {##} - 2 &, {3, 3}]]], {m, (2^nn)^2}]]

A163363 Hilbert curve in N X N grid, one-based, starting downwards from the top-left corner.

Original entry on oeis.org

1, 4, 2, 5, 3, 15, 6, 8, 14, 16, 59, 7, 9, 13, 17, 60, 58, 10, 12, 18, 20, 61, 57, 55, 11, 31, 19, 21, 64, 62, 56, 54, 32, 30, 24, 22, 65, 63, 51, 53, 33, 29, 25, 23, 235, 66, 68, 50, 52, 34, 36, 28, 26, 234, 236, 79, 67, 69, 49, 47, 35, 37, 27, 231, 233, 237, 80, 78, 72

Offset: 1

Antti Karttunen, Jul 29 2009

Antti Karttunen, Table of n, a(n) for n = 1..32896
Index entries for sequences that are permutations of the natural numbers

Inverse: A163364. Transpose: A163361.

a(n) = A163359(n-1) + 1.

A276391 G.f. satisfies A(x) - 4*A(x^2) = x/(1+x).

Original entry on oeis.org

1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 683, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 2731, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 683, 1, 3, 1, 11, 1, 3

Offset: 1

Bill Gosper, Sep 07 2016

Describes one of the two patterns of spacings of preimages of quadruple points of the Hilbert curve, H(t), 0 <= t <= 1. If H fills the complex unit square [0,1] X [0,i], H(0)=0, H(1)=1, then 1/2 + i/4 is a quadruple point with preimages t in {5/48, 7/48, 41/48, 43/48}. If we can characterize the rest of the quadruple points along the vertical bisector 1/2 + iy, all the rest are generated recursively by the to-quadrant maps (H/i + i)/2, (H + i)/2, (H + i + 1)/2, and (i H + 2)/2. Julian Ziegler Hunts has privately observed that H = 1/2 + ir is a quadruple point for all dyadic rational r in (0,1/2). E.g., the 31 r with denominator 64, i.e., 1/64, 3/64, ..., 31/64 generate preimage 4-tuples
   {{1025, 1027, 11261, 11263}, {1037, 1039, 11249, 11251},
   {1073, 1075, 11213, 11215}, {1085, 1087, 11201, 11203},
   {1217, 1219, 11069, 11071}, {1229, 1231, 11057, 11059},
   {1265, 1267, 11021, 11023}, {1277, 1279, 11009, 11011},
   {1793, 1795, 10493, 10495}, {1805, 1807, 10481, 10483},
   {1841, 1843, 10445, 10447}, {1853, 1855, 10433, 10435},
   {1985, 1987, 10301, 10303}, {1997, 1999, 10289, 10291},
   {2033, 2035, 10253, 10255}, {2045, 2047, 10241, 10243}}/12288
  with differences
   {{1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}, {11, 11, -11, -11},
   {1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}, {43, 43, -43, -43},
   {1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}, {11, 11, -11, -11},
   {1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}}/1024
But the r in (1/2,1) are 1/6th as dense. The relevant quadruple points with denominator 2^n are 1/2 + i (6k - mod(5^n, 12))/2^n, 1 <= k < 2^n/6. E.g., if n = 6, then r is in {37/64, 43/64, 49/64, 55/64, 61/64} and the preimage 4-tuples of 1/2 + ir have differences {{-11, -11, 11, 11}, {-1, -1, 1, 1}, {-3, -3, 3, 3}, {-1, -1, 1, 1}}5/1024 (the reverse of) probably just -5*(this sequence).

			A(4) = 11. Thus
Table[unbert[1/2 + (2*4+1) I/2^n] - unbert[1/2 + (2*4-1) I/2^n], {n, 5, 9}]
{{11/256, 11/256, -11/256, -11/256},
{11/1024, 11/1024, -11/1024, -11/1024},
{11/4096, 11/4096, -11/4096, -11/4096},
{11/16384, 11/16384, -11/16384, -11/16384},
{11/65536, 11/65536, -11/65536, -11/65536}}
where unbert(H(t)) = {t}, the multivalued inverse Hilbert function (with I = sqrt(-1). See the definition of unbert[] in the MATHEMATICA section.
Note that this table must have n > 4, lest (2*4+1)/2^n > 1/2.

Alois P. Heinz, Table of n, a(n) for n = 1..16383
Bill Gosper, Connect-the-dots exact samplings of Hilbert's spacefiller
Nicholas J. Rose, Hilbert-Type Space-Filling Curves. [Wayback Machine link]

Cf. A000007, A000695, A001511, A007583, A115716, A163361, A260482.

a:= proc(n) option remember; `if`(n=0, 0,
      `if`(n::odd, 1, 4*a(n/2)-1))
    end:
seq(a(n), n=1..100); # Alois P. Heinz, Sep 07 2016

(* Cf. the numerators of Out[339], below*)
hilbert[t_] :=
piecewiserecursivefractal[t, Identity, {Min[4, 1 + Floor[4*#]]} &,
    {1 - 4*# &, 4*# - 1 &, 4*# - 2 &, 4 - 4*# &},
    {I*(1 - #)/2 &, (I + #)/2 &, (I + 1 + #)/2 &, 1 + #*I/2 &}]
(* E.g., hilbert[1/2] {1/2 + I/2} *)
unbert[z_] :=
piecewiserecursivefractal[z, Identity,
     If[0 <= Re[#] <= 1 && 0 <= Im[#] <= 1,
   Range[4], {}] &,
    {1 - 2*#/I &, 2*# - I &, 2*# - I - 1 &, (# - 1)*2/I &},
    {(1 - #)/4 &, (# + 1)/4 &, (# + 2)/4 &, 1 - #/4 &}]
(* unbert[1/2 + I/2] {1/6, 1/2, 5/6} a triple point: hilbert/@% {{1/2 + I/2}, {1/2 + I/2}, {1/2 + I/2}} *)
ClearAll[piecewiserecursivefractal];
piecewiserecursivefractal[x_, f_, which_, iters_, fns_] :=
CheckAbort[
  Check[piecewiserecursivefractal[x, g_, which, iters,
     fns] = ((piecewiserecursivefractal[x, h_, which, iters, fns] :=
       Block[{y}, y /. Solve[f[y] == h[y], y]]);
     Union @@ ((fns[[#]] /@
           piecewiserecursivefractal[iters[[#]][x],
            Composition[f, fns[[#]]], which, iters, fns]) & /@
        which[x])),
   Abort[], {$RecursionLimit::reclim, $RecursionLimit::reclim2}],
  piecewiserecursivefractal[x, g_, which, iters, fns] =.; Abort[]]
(* For a simpler but less bulletproof version, see the MATHEMATICA section of A260482 *)
In[338]:= unbert /@ (1/2 + I Range[1/32, 15/32, 1/16])
Out[338]= {{257/3072, 259/3072, 2813/3072, 2815/3072},
             {269/3072, 271/3072, 2801/3072, 2803/3072},
             {305/3072, 307/3072, 2765/3072, 2767/3072},
             {317/3072, 319/3072, 2753/3072, 2755/3072},
             {449/3072, 451/3072, 2621/3072, 2623/3072},
             {461/3072, 463/3072, 2609/3072, 2611/3072},
             {497/3072, 499/3072, 2573/3072, 2575/3072},
             {509/3072, 511/3072, 2561/3072, 2563/3072}}
In[339]:= Differences@%
Out[339]= {{1/256, 1/256, -1/256, -1/256},
             {3/256, 3/256, -3/256, -3/256},
             {1/256, 1/256, -1/256, -1/256},
             {11/256, 11/256, -11/256, -11/256},
             {1/256, 1/256, -1/256, -1/256},
             {3/256, 3/256, -3/256, -3/256},
             {1/256, 1/256, -1/256, -1/256}}
(* Check that %338[[1]] is a quadruple point *)
In[340]:= hilbert /@ %%[[1]]
Out[340]= {{1/2 + I/32}, {1/2 + I/32}, {1/2 + I/32}, {1/2 + I/32}}
In[341]:= Select[Range[0, 1, 1/512], Length[unbert[# + I/2] > 3] &]
Out[341]= {}
(* I.e., there aren't any quadruple points on the horizontal bisector of the unit square! Other such horizontal and vertical lines of dyadic rationals intersect a dense set of quadruple points. *)
a[n_] := (2^(2*IntegerExponent[n, 2]+1) + 1)/3; Array[a, 100] (* Amiram Eldar, Dec 18 2023 *)

a(n)= fromdigits(binary(n), 4)-fromdigits(binary(n-1), 4) \\ Bill McEachen, Dec 20 2024

a(n) = (2 + 4^A001511(n))/6.
G.f.: A(x) - 4*A(x^2) = x/(1+x).
From Alois P. Heinz, Sep 07 2016: (Start)
a(2^n) = A007583(n).
a(2^n+n) = a(n) + A000007(n).
(a(2*n)+1)/4 = a(n) for n>0. (End)
a(n) = A000695(n) - A000695(n-1). - Bill McEachen, Oct 30 2020
G.f.: Sum_{k>=0} 4^k * x^(2^k) / (1 + x^(2^k)). - Ilya Gutkovskiy, Dec 14 2020

Keyword:mult added by Andrew Howroyd, Aug 06 2018

cp's OEIS Frontend

A163362 Inverse permutation to A163361.

Views

Author

Keywords

Links

Crossrefs

Formula

A163357 Hilbert curve in N X N grid, starting rightwards from the top-left corner, listed by descending antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326409 Minesweeper sequence of positive integers arranged on a 2D grid along Hamiltonian path.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A163363 Hilbert curve in N X N grid, one-based, starting downwards from the top-left corner.

Views

Author

Keywords

Links

Crossrefs

Formula

A276391 G.f. satisfies A(x) - 4*A(x^2) = x/(1+x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions