0
$\begingroup$

http://blog.garritys.org/2012/12/base-i-1-there-be-dragons.html

As the link above shows, it's possible to represent every Gaussian integer by converting a number N into its binary representation and then expressing it in base (i-1). The number N can be considered a point of the graph.

This process generates a dragon curve, and what I'd like to know is the sum of bits that correspond to the binary representation of each point in a given range $[(-a,a),(-a,a)]$.

For example, in the range $[(-1,1),(-1,1)]$ the sum of bits would be $20$, since the sum of bits $S_{b}$ in each vertex is:

$S_{b}(1) = 1$

$S_{b}(2) = 1$

$S_{b}(3) = 2$

$S_{b}(6) = 2$

$S_{b}(7) = 3$

$S_{b}(14) = 3$

$S_{b}(29) = 4$

$S_{b}(58) = 4$

So the total sum of bits $S_{t}(1) = 20$ ($58$ is not plotted in the graphic shown in the article, but it would represent $-i+1$, the only point missing).

The following link provides information regarding the twindragon curve and its generation: https://metacpan.org/pod/Math::PlanePath::ComplexMinus#DESCRIPTION

In the "DESCRIPTION" section, it explains the pattern that assigns the values of a certain range of the dragon curve.

N=0 to N=7 N=8 to N=15 repeat shape 2 3 10 11 0 1 8 9 6 7 14 15 4 5 12 13

$(i-1)^3 = 2+2i$ so the pattern in the right starts with $8$ in $X=2,Y=2$-

I'm almost certain that this is all the information needed to calculate the sum of the bits within a given range. However, I don't know exactly what this particular approach should be.

$\endgroup$
5
  • $\begingroup$ I computed some bit sums but so far couldn't find an easy pattern to this: OEIS yields no match, and it's no a simple polynomial relation either. The first few terms (up to $a=50$) are 20, 75, 175, 310, 515, 750, 1065, 1380, 1795, 2265, 2815, 3355, 4045, 4755, 5560, 6285, 7170, 8110, 9175, 10235, 11465, 12695, 14030, 15255, 16710, 18250, 19910, 21500, 23305, 25095, 26940, 28585, 30510, 32490, 34655, 36755, 39145, 41505, 44045, 46405, 49085, 51800, 54685, 57410, 60440, 63385, 66435, 69175, 72325, 75540. $\endgroup$ Commented May 1, 2015 at 12:10
  • $\begingroup$ I can confirm your answers, I'll take a look at your code! Just out of curiosity, could you tell me how long it takes for N = 500? $\endgroup$ Commented May 1, 2015 at 12:20
  • $\begingroup$ It does N = 500 in about a third of a second on my notebook. N = 5000 took 42 seconds. $\endgroup$ Commented May 1, 2015 at 12:27
  • $\begingroup$ Bit if I remember to let my compiler optimize the code (passing -O3 to g++) then N = 5000 completes in 16 seconds. $\endgroup$ Commented May 1, 2015 at 12:35
  • $\begingroup$ Excellent. My previous solution took 17 seconds for N = 500 so yours is much better. I have a feeling there's a much faster way that we're both missing though, unfortunately. $\endgroup$ Commented May 1, 2015 at 12:37

1 Answer 1

Reset to default
1
$\begingroup$

I've computed the bit sums up to $n=10{,}000$, and plotted them to get an idea of what the data looks like. At first it doesn't look too bad: the data (blue) gives a fairly smooth curve, which can be approximated quite well with a cubic curve (red):

First plot of data

But then I looked closer, and plotted the difference between two consecutive values of $n$. That would be the bit count of the rim of one square, instead of its interior. Now deviations from the smooth curve become visible:

Plot of differences

The red curve is again a cubic least squares approximation of that. If I only look at the residue with respect to that cubic approximation, the fractal structure of the data becomes even more pronounced:

Plot of residue

Any solution to this question would have to capture the fractal structure exposed by this plot. I very much doubt that there is some reasonable easy closed formula to achieve this. Therefore despite the fact that this post here doesn't really provide the formula you're asking for, I fear that it might be the best answer you can expect in the forseeable future.

$\endgroup$
1
  • $\begingroup$ It seems the answer lies in focusing on using recursion on the sum itself instead of doing it for every number in the specified range. I have no idea how the sum itself could contain the correct answer though. $\endgroup$ Commented May 1, 2015 at 18:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.