2
$\begingroup$

I have a function which produces a series from an integer. I currently do this iteratively.

f(0) =           []
f(1) =          [0]
f(2) =       [0, 0]
f(3) =       [0, 1]
f(4) =    [0, 0, 1]
f(5) =    [0, 1, 1]
f(6) =    [0, 0, 2]
f(7) =    [0, 1, 2]
f(8) = [0, 0, 1, 2]

There is another pattern here.

          []                             = 0
         [0]                        2**0 = 1 
      [0, 0]                 2**0 + 2**0 = 2
      [0, 1]                 2**0 + 2**1 = 3
   [0, 0, 1]          2**0 + 2**0 + 2**1 = 4
   [0, 1, 1]          2**0 + 2**1 + 2**1 = 5
   [0, 0, 2]          2**0 + 2**0 + 2**2 = 6
   [0, 1, 2]          2**0 + 2**1 + 2**2 = 7
[0, 0, 1, 2]   2**0 + 2**0 + 2**1 + 2**2 = 8

(Where double asterisk means 'raised to the power.)

Is there way to get from the argument, straight to the series, without working out all of the previous series?


Update, thanks for the interest.

Here's some Javascript code which generates the sequences, where weight is the sequence:

var numbers = [];

for (var count = 0; count < 20; count++) {
  for (var i = numbers.length; i > 0; i--) {
    if (count % (2**i) === 0) {
      numbers[i] = numbers[i - 1];
    }
  }
  numbers[0] = count;

  var weights = [];
  for (var j = 1; j < numbers.length; j++) {
    // note the differences below are all exact powers of 2
    weights[j] = Math.log2(numbers[j - 1] - numbers[j]);
  }
  if (numbers.length > 0) {
    weights[0] = 0;
  }

  console.log(`count ${count} numbers ${numbers} weight ${weights}`);
}

and the output:

count 0 numbers             0 weight          
count 1 numbers             1 weight         0
count 2 numbers           2,1 weight       0,0
count 3 numbers           3,1 weight       0,1
count 4 numbers         4,3,1 weight     0,0,1
count 5 numbers         5,3,1 weight     0,1,1
count 6 numbers         6,5,1 weight     0,0,2
count 7 numbers         7,5,1 weight     0,1,2
count 8 numbers       8,7,5,1 weight   0,0,1,2
count 9 numbers       9,7,5,1 weight   0,1,1,2
count 10 numbers     10,9,5,1 weight   0,0,2,2
count 11 numbers     11,9,5,1 weight   0,1,2,2
count 12 numbers    12,11,9,1 weight   0,0,1,3
count 13 numbers    13,11,9,1 weight   0,1,1,3
count 14 numbers    14,13,9,1 weight   0,0,2,3
count 15 numbers    15,13,9,1 weight   0,1,2,3
count 16 numbers 16,15,13,9,1 weight 0,0,1,2,3
count 17 numbers 17,15,13,9,1 weight 0,1,1,2,3
count 18 numbers 18,17,13,9,1 weight 0,0,2,2,3
count 19 numbers 19,17,13,9,1 weight 0,1,2,2,3

There seems to be an emergent restriction that the values in the Nth place of the series can only take values between 0 and N.

$\endgroup$

closed as unclear what you're asking by Winther, Namaste, Lord Shark the Unknown, Jyrki Lahtonen, José Carlos Santos Jul 27 '18 at 14:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ The pattern looks like: if there are no pairs of repeated digits add a zero to the left, if there are double digits increment the right most digit and set the left of the pair to zero. Am I right in thinking then that $f(9)=[0,1,1,2],f(10)=[0,0,2,2]$? I can't see what to then do for f(11) because there are two pairs of repeated digits, it could be $[0,0,0,3]$ or $[0,1,2,2]$, I wouldn't know how to deal with a triple digit, so I guess it would be $[0,1,2,2]$. $\endgroup$ – Benedict W. J. Irwin Jul 26 '18 at 12:59
  • 1
    $\begingroup$ Following that rule through large numbers seem to end in long strings of [...,0,3,0,3,0,3,0,3] etc. $\endgroup$ – Benedict W. J. Irwin Jul 26 '18 at 13:09
  • 1
    $\begingroup$ @BenedictWilliamJohnIrwin Thanks for your interest, I've posted an update. $\endgroup$ – fadedbee Jul 26 '18 at 13:36
  • $\begingroup$ @Winther Yes, it is well defined. I've posted a javascript function which generates the series in an update. $\endgroup$ – fadedbee Jul 26 '18 at 14:05
1
$\begingroup$

I have code in PARI/GP which is easy to translate:

{f(n) = if( n<=0, [], my(m = exponent(n)); 
        vector(m+1, j, my(i = j-2); if(i<0, 0, n\(2^i)%2 + i)))};

Here $\ \texttt{exponent(n) = floor(Log(2,n)).} \ $ Equvalent Mathematica code:

f[n_] := If[ n<=0, {}, With[{m = IntegerLength[n, 2] - 1},
         Table[ If[ i<0, 0, Mod[Quotient[n, 2^i], 2] + i], {i, -1, m-1}]]];
$\endgroup$
  • $\begingroup$ Thanks for a great answer. How did you work it out? $\endgroup$ – fadedbee Jul 27 '18 at 9:34
  • 1
    $\begingroup$ I observed the pattern of the first digit (always 0), the 2nd digit (alternating 0,1), and so on. Then I wrote the code to implement those patterns. $\endgroup$ – Somos Jul 27 '18 at 10:33
1
$\begingroup$

This is just a translation of @Somos' answer.

function f(n) {
  if (n <= 0) return [];
  const m = Math.log2(n);
  for (var j = 0, ret = []; j <= m; j++) {
    var i = j - 1;
    if (i < 0) {
      ret[j] = 0;
    } else {
      ret[j] = Math.floor((n / 2**i) % 2 + i);
    }
  }
  return ret;
}
for (var n = 0; n < 20; n++) {
  console.log(`n ${n}, series ${f(n)}`);
}

It outputs:

n 0, series 
n 1, series 0
n 2, series 0,0
n 3, series 0,1
n 4, series 0,0,1
n 5, series 0,1,1
n 6, series 0,0,2
n 7, series 0,1,2
n 8, series 0,0,1,2
n 9, series 0,1,1,2
n 10, series 0,0,2,2
n 11, series 0,1,2,2
n 12, series 0,0,1,3
n 13, series 0,1,1,3
n 14, series 0,0,2,3
n 15, series 0,1,2,3
n 16, series 0,0,1,2,3
n 17, series 0,1,1,2,3
n 18, series 0,0,2,2,3
n 19, series 0,1,2,2,3
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.