a simple formula

Question

Hi, I have a for loop which gives a given integer sequence, for fixed parameters N and D :

    int i = 0, j = 0;
    for (int k=0; k<N; k++) {             
      sequence[k] = i;
      if ((i += D) >= N) i = ++j;
    }

I'd like to find a simple formula which reproduces this sequence, depending only on N and D (and the index k), like sequence[k] = D*(k%D)+ k/D (which doesn't work). I tried hard but I just can't find something which always work for any value of N and D!

Thanks!

Answer 1

I think the following should do:

sequence[0] = 0;

For k!=0,
sequence[k] = (sequence[k-1]+D)%N;
sequence[k] = ( (temp=(sequence[k-1]+D)) / N)? ++sequence[0]: temp%N;

Here, temp is a temporary variable, introduced to avoid redundancy in the expression on the RHS.

I know it's complex, but I'm sure this one's correct. After all the values are set, you can reset sequence[0] to 0 and there you go.

PS: I'm trying to get a closed form.

Answer 2

Here's the formula. At the moment it requires a conditional statement, but you can always express it via a function returning 0 or 1 if you want pure functional form.

I wrote it as Perl function, to ease testing (I tested for all N<=20 and D between 0 and N)

sub div { my ($x, $y) = @_; return ($x-$x%$y)/$y }; # whole division

my $small_subsequence_length = div($N, $D);
my $big_subsequence_length = $small_subsequence_length + 1;
my $num_big_subseqiences = $N % $D;
my $num_total_big_subsequence_numbers = $big_subsequence_length * $num_big_subseqiences;
my $num_total_small_subsequence_numbers = $N - $num_total_small_subsequence_numbers;
my $num_small_subseqiences = div($num_total_small_subsequence_numbers, $small_subsequence_length);

sub sequence {
    my $k = $_[0];
    my ($subsequence_num, subsequence_offset);

    if ($k > $num_total_big_subsequence_numbers) {
        my $k2 = $k - $num_total_big_subsequence_numbers;
        $subsequence_num = div($k2, $small_subsequence_length) + $num_big_subseqiences;
        $subsequence_offset = ($k2 % $small_subsequence_length) * $D;
    } else {
        $subsequence_num = div($k, $big_subsequence_length);
        $subsequence_offset = ($k % $big_subsequence_length) * $D;
    }
    return $subsequence_offset + $subsequence_num;
}

Answer 3

Converted DVK's function to C-code, and removed the branch:

int sequence(int N, int D, int k) {
    int subsequence_length = N / D + 1;
    int num_big_subseqiences = N % D;
    int num_total_big_subsequence_numbers = subsequence_length * num_big_subseqiences;

    int small = (k > num_total_big_subsequence_numbers) & 1;

    k -= num_total_big_subsequence_numbers * small;
    subsequence_length -= small;
    subsequence_num = (k / subsequence_length) + num_big_subseqiences * small;
    subsequence_offset = (k % subsequence_length) * D;

    return subsequence_offset + subsequence_num;
}