Sequence of numbers which follow a rule

Question

I have a sequence of numbers: 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4,... I have to guess the rule which the sequence follow and to:

• Compute the sum of all prime numbers smaller than n
• Find how many times the digit k appears in the element of the sequence

• The number on the position p in the sequence.

  Input:

• n, k, p

  I have written the next code: it serves it's purpose, but I would like you to give me some tips on code style and performance(and I am thinking specifically to speed).

  #include <stdio.h>
  #include <stdlib.h>
  int prime(int n)
  {
   if(n < 2) return 0;
   if(n == 2) return 1;
   if(n % 2 == 0) return 0;
   int i;
   for(i = 3; i <= sqrt(n); i += 2)
   {
   if(n % i == 0)
   return 0;
   }
   return 1;
  }
  int main()
  {
   int n;
   int p;
   int k;
   scanf( "%d", &n );
   scanf( "%d", &k );
   scanf( "%d", &p );
   int primeSumPerSubSequence = 128;
   int nAux = n;
   int primeSum = 0;
   int subSequences = 0;
   if( n > 60 )
   subSequences = n / 60;
   if( n > 60 )
   {
   nAux = n % 60;
   primeSum = primeSum + primeSumPerSubSequence * subSequences;
   }
   int i = 2;
   int firstNumber = 1;
   int secondNumber = 2;
   if( !nAux ) secondNumber = 0;
   int thirdNumber = 3;
   int kFound = 0;
   switch( k )
   {
   case 0: kFound = 4 * subSequences;break;
   case 1: kFound = 8 * subSequences;break;
   case 2: kFound = 4 * subSequences;break;
   case 3: kFound = 8 * subSequences;break;
   case 4: kFound = 4 * subSequences;break;
   case 5: kFound = 8 * subSequences;break;
   case 6: kFound = 4 * subSequences;break;
   case 7: kFound = 8 * subSequences;break;
   case 8: kFound = 4 * subSequences;break;
   case 9: kFound = 8 * subSequences;break;
   }
   if(( kFound == 1 ) || ( kFound == 2 )) kFound++;
   int pNumber = -1;
   if( !p ) pNumber = 0;
   else if( p % 60 == 0) pNumber = 1;
   else if( p > 60 ) p %= 60;
   while( i <= nAux )
   {
   if( nAux && prime( secondNumber ) )
   {
   primeSum += secondNumber;
   }
   if(( i == p ) && ( pNumber != 1)) pNumber = secondNumber;
   firstNumber = secondNumber;
   secondNumber = thirdNumber;
   thirdNumber = firstNumber + secondNumber;
   if( thirdNumber > 9 )
   thirdNumber %= 10;
   if(( secondNumber == k ) && ( i < n )) kFound++;
   i++;
   }
   firstNumber = 1;
   secondNumber = 2;
   thirdNumber = 3;
   if( pNumber == -1 )
   {
   for( i = 3; i <= p; i++ )
   {
   firstNumber = secondNumber;
   secondNumber = thirdNumber;
   thirdNumber = firstNumber + secondNumber;
   if( thirdNumber > 9 )
   thirdNumber %= 10;
   if( i == p ) pNumber = secondNumber;
   }
   }
   if( pNumber == -1) pNumber = 0;
   printf( "\n%d", primeSum );
   printf( "\n%d", kFound );
   printf( "\n%d", pNumber );
   return 0;
  }
  

Should I edit the question and add how I thought the algorithm? Thank you and please excuse my bad english.

• jrh: Hi Timʘɫei, it looks like you are missing a few #includes, I would recommend editing the code in your post to add those in (i.e., stdio.h and wherever prime() is from).
• Emily L.: Please explain your algorithm for the sequence.
• Timʘtei: @EmilyL. By that you mean the rule of the sequence? The rule is the following: each number is the last digit of the sum of the two previous numbers. 5 + 8 = 3(13 % 10)

Answer 1

This is a rare case where the comment is absolutely necessary, along the lines of

/* The sequence is Fibonacci numbers modulo 10. It is periodic with a
 period of 60. Each even digits appears for 4 times, and each odd
 digit for 8 times, per period. The sum of primes per period is 128.
 Reviewer's note: are you sure? Looks like you consider 1 as prime.
 To get the desired results, compute the number of entire periods,
 and process the last incomplete part separately. */

• Rename subSequences toperiods

• Collapse the switch to

  kFound = ((k & 0x01)? 8: 4) * periods;
  

• I don't see how kFound can be 1 or 2, so

  if(( kFound == 1 ) || ( kFound == 2 )) kFound++;
  

  seems to serve no purpose. Correct me if I am wrong.

• Working with the incomplete part should be split into functions. Precompute the period once, and pass it to separate functions (computing sum of primes, counting occurrences, and returning number at position).

• Timʘtei: Thank you! I have changed if(( kFound == 1 ) || ( kFound == 2 )) kFound++; to if(( k == 1 ) || ( k == 2 )) kFound++;. I understood what you said, but I do not understand the condition (k & 0x01) in the ternary operator.
• vnp: @Timʘɫei The condition tests odd vs even.
• Timʘtei: I understand that, but I do not understand what does 0x01 mean.
• jrh: @Timʘtei 0x01 is just the value 1 in hexadecimal. See the Integer Literal article on cppreference.com for more information. vnp probably made it a hex literal just to emphasize that it's a bitwise / masking operation.