Sum digits of previous numbers algorithm in C#-CodePudding

I have sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10... Each number then is the sum of the separete digits of the previous elements. It's a bit like Fibonacci.. I want to write a function

int FindSimilarFibo(int x)
{
//x = 10 return 10
//x = 6  return 8
}

I wrote this, but I can't figure out the correct algorithm:

int FindSimilarFibo(int x) {
    int p = 0;
    int q = 1;
    for (int i = 0; i < n; i  )
{
    int temp = p;
    p = q;
    q = temp   q;
    if (q > 9) 
    {
        int leftQ = q % 10;
        int rightQ = q / 10;
        q = leftQ   rightQ;
        q = temp   q;

    }
    if (p > 9)
    {
        int leftQ = q % 10;
        int rightQ = q / 10;
        temp = leftQ   rightQ;
        p = q;
        q = temp   q;
    }

}
    return p;
}

CodePudding user response：

The problem looks to be that you're overwriting previous values when computing the digits-sum of the next; so... don't do that? perhaps:

static int FindSimilarFibo(int n)
{
    int p = 0;
    int q = 1;
    for (int i = 0; i < n; i  )
    {
        var next = SumDigits(p)   SumDigits(q);
        p = q;
        q = next;
    }
    return p;

    static int SumDigits(int value)
    {
        int sum = 0;
        while (value > 9)
        {
            sum  = value % 10;
            value /= 10;
        }
        return sum   value;
    }
}

CodePudding user response：

If you search for your sequence at the The Online Encyclopedia of Integer Sequences you will find this at A010077.

One implementation is given as

a(n) = floor(a(n-1)/10)   floor(a(n-2)/10)   (a(n-1) mod 10)   (a(n-2) mod 10)

Or in c#

public int A010077(int n)
{
    int n_2 = 0;
    int n_1 = 1;
    int value = 0;
    
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    
    for (int i=0; i<n-1; i  )
    {
        value = (n_1 / 10)   (n_2 / 10)   (n_1 % 10)   (n_2 % 10);
        n_2 = n_1;
        n_1 = value;
    }
    
    return value;
}

For example

Enumerable.Range(1, 20).Select(A010077)

gives

1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6

CodePudding user response：

If you print out all the values of this sequence, you'll see this:

0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6, 11, 8, 10, 9, 10, 10, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6, 11, 8, 10, 9, 10, 10

Inspection reveals that the sequence repeats starting with 2, 3, 5, 8 and ending with 10, 9, 10, 10.

Given this, we can write a non-looping solution like this:

public static int FindSimilarFibo(int x)
{
    if (x == 0)
        return 0;

    if (x <= 2)
        return 1;

    int[] values = { 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6, 11, 8, 10, 9, 10, 10 };

    return values[(x   values.Length - 3) % values.Length];
}