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

%I #69 Dec 18 2023 01:44:07

%S 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,

%T 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,

%U 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

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

%C 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

%C {{1025, 1027, 11261, 11263}, {1037, 1039, 11249, 11251},

%C {1073, 1075, 11213, 11215}, {1085, 1087, 11201, 11203},

%C {1217, 1219, 11069, 11071}, {1229, 1231, 11057, 11059},

%C {1265, 1267, 11021, 11023}, {1277, 1279, 11009, 11011},

%C {1793, 1795, 10493, 10495}, {1805, 1807, 10481, 10483},

%C {1841, 1843, 10445, 10447}, {1853, 1855, 10433, 10435},

%C {1985, 1987, 10301, 10303}, {1997, 1999, 10289, 10291},

%C {2033, 2035, 10253, 10255}, {2045, 2047, 10241, 10243}}/12288

%C with differences

%C {{1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}, {11, 11, -11, -11},

%C {1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}, {43, 43, -43, -43},

%C {1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}, {11, 11, -11, -11},

%C {1, 1, -1, -1}, {3, 3, -3, -3}, {1, 1, -1, -1}}/1024

%C 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).

%H Alois P. Heinz, <a href="/A276391/b276391.txt">Table of n, a(n) for n = 1..16383</a>

%H Bill Gosper, <a href="http://www.tweedledum.com/rwg/sampeano.htm">Connect-the-dots exact samplings of Hilbert's spacefiller</a>

%H Nicholas J. Rose, <a href="https://web.archive.org/web/20151010184939/http://www4.ncsu.edu/~njrose/pdfFiles/HilbertCurve.pdf">Hilbert-Type Space-Filling Curves</a>. [Wayback Machine link]

%F a(n) = (2 + 4^A001511(n))/6.

%F G.f.: A(x) - 4*A(x^2) = x/(1+x).

%F From _Alois P. Heinz_, Sep 07 2016: (Start)

%F a(2^n) = A007583(n).

%F a(2^n+n) = a(n) + A000007(n).

%F (a(2*n)+1)/4 = a(n) for n>0. (End)

%F a(n) = A000695(n) - A000695(n-1). - _Bill McEachen_, Oct 30 2020

%F G.f.: Sum_{k>=0} 4^k * x^(2^k) / (1 + x^(2^k)). - _Ilya Gutkovskiy_, Dec 14 2020

%e A(4) = 11. Thus

%e Table[unbert[1/2 + (2*4+1) I/2^n] - unbert[1/2 + (2*4-1) I/2^n], {n, 5, 9}]

%e {{11/256, 11/256, -11/256, -11/256},

%e {11/1024, 11/1024, -11/1024, -11/1024},

%e {11/4096, 11/4096, -11/4096, -11/4096},

%e {11/16384, 11/16384, -11/16384, -11/16384},

%e {11/65536, 11/65536, -11/65536, -11/65536}}

%e where unbert(H(t)) = {t}, the multivalued inverse Hilbert function (with I = sqrt(-1). See the definition of unbert[] in the MATHEMATICA section.

%e Note that this table must have n > 4, lest (2*4+1)/2^n > 1/2.

%p a:= proc(n) option remember; `if`(n=0, 0,

%p `if`(n::odd, 1, 4*a(n/2)-1))

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Sep 07 2016

%t (* Cf. the numerators of Out[339], below*)

%t hilbert[t_] :=

%t piecewiserecursivefractal[t, Identity, {Min[4, 1 + Floor[4*#]]} &,

%t {1 - 4*# &, 4*# - 1 &, 4*# - 2 &, 4 - 4*# &},

%t {I*(1 - #)/2 &, (I + #)/2 &, (I + 1 + #)/2 &, 1 + #*I/2 &}]

%t (* E.g., hilbert[1/2] {1/2 + I/2} *)

%t unbert[z_] :=

%t piecewiserecursivefractal[z, Identity,

%t If[0 <= Re[#] <= 1 && 0 <= Im[#] <= 1,

%t Range[4], {}] &,

%t {1 - 2*#/I &, 2*# - I &, 2*# - I - 1 &, (# - 1)*2/I &},

%t {(1 - #)/4 &, (# + 1)/4 &, (# + 2)/4 &, 1 - #/4 &}]

%t (* 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}} *)

%t ClearAll[piecewiserecursivefractal];

%t piecewiserecursivefractal[x_, f_, which_, iters_, fns_] :=

%t CheckAbort[

%t Check[piecewiserecursivefractal[x, g_, which, iters,

%t fns] = ((piecewiserecursivefractal[x, h_, which, iters, fns] :=

%t Block[{y}, y /. Solve[f[y] == h[y], y]]);

%t Union @@ ((fns[[#]] /@

%t piecewiserecursivefractal[iters[[#]][x],

%t Composition[f, fns[[#]]], which, iters, fns]) & /@

%t which[x])),

%t Abort[], {$RecursionLimit::reclim, $RecursionLimit::reclim2}],

%t piecewiserecursivefractal[x, g_, which, iters, fns] =.; Abort[]]

%t (* For a simpler but less bulletproof version, see the MATHEMATICA section of A260482 *)

%t In[338]:= unbert /@ (1/2 + I Range[1/32, 15/32, 1/16])

%t Out[338]= {{257/3072, 259/3072, 2813/3072, 2815/3072},

%t {269/3072, 271/3072, 2801/3072, 2803/3072},

%t {305/3072, 307/3072, 2765/3072, 2767/3072},

%t {317/3072, 319/3072, 2753/3072, 2755/3072},

%t {449/3072, 451/3072, 2621/3072, 2623/3072},

%t {461/3072, 463/3072, 2609/3072, 2611/3072},

%t {497/3072, 499/3072, 2573/3072, 2575/3072},

%t {509/3072, 511/3072, 2561/3072, 2563/3072}}

%t In[339]:= Differences@%

%t Out[339]= {{1/256, 1/256, -1/256, -1/256},

%t {3/256, 3/256, -3/256, -3/256},

%t {1/256, 1/256, -1/256, -1/256},

%t {11/256, 11/256, -11/256, -11/256},

%t {1/256, 1/256, -1/256, -1/256},

%t {3/256, 3/256, -3/256, -3/256},

%t {1/256, 1/256, -1/256, -1/256}}

%t (* Check that %338[[1]] is a quadruple point *)

%t In[340]:= hilbert /@ %%[[1]]

%t Out[340]= {{1/2 + I/32}, {1/2 + I/32}, {1/2 + I/32}, {1/2 + I/32}}

%t In[341]:= Select[Range[0, 1, 1/512], Length[unbert[# + I/2] > 3] &]

%t Out[341]= {}

%t (* 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. *)

%t a[n_] := (2^(2*IntegerExponent[n, 2]+1) + 1)/3; Array[a, 100] (* _Amiram Eldar_, Dec 18 2023 *)

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

%K nonn,easy,mult

%O 1,2

%A _Bill Gosper_, Sep 07 2016

%E Keyword:mult added by _Andrew Howroyd_, Aug 06 2018