Sunday, April 4, 2010

Solution - #104 Project Euler

//p104
// Find the Fibonacci sequence for which the first nine digits and the last nine digits are 1-9 pandigital

#include
#include

char number_string[100000];

char isPandigital( unsigned long int num )
{
   if ( num < 123456789 )
   {
      return 0;
   }

   char num_of_unique_digits = 0;

   char number_array[9];

   unsigned long int temp = num;

   int i;
   int j;

   for ( i = 0; i < 9; i++ )
   {
      number_array[i] = temp - ((temp / 10) * 10);
      if ( number_array[i] == 0 )
      {
         return 0;
      }

      temp /= 10;
   }

   char is_unique = 1;

   for ( i = 0; i < 9; i++ )
   {
      for ( j = 0; j < 9; j++ )
      {
         if ( i != j )
         {
            if ( number_array[i] == number_array[j] )
            {
               is_unique = 0;
            }
         }
      }

      if ( is_unique )
      {
         num_of_unique_digits++;
      }

      is_unique = 1;
   }

   if ( num_of_unique_digits == 9 )
   {
      return 1;
   }
   else
   {
      return 0;
   }
}

int numOfDigits( mpz_t num )
{
   int num_of_digits = 0;

   char *number_pointer;
   mpz_get_str( number_string, 10, num );

   number_pointer = number_string;

   while( *number_pointer != '\0' )
   {
      num_of_digits++;
      number_pointer++;
   }

   return num_of_digits;
}

char areBothSidesPandigital( mpz_t num )
{
   mpz_t mod;
   mpz_init_set_str( mod, "1000000000", 10 );

   mpz_t temp;
   mpz_init( temp );

   unsigned long int number_group = 0;

   mpz_mod( temp, num, mod );

   number_group = mpz_get_ui( temp );

   if ( isPandigital( number_group ) )
   {
      mpz_ui_pow_ui( temp, 10, (numOfDigits( num ) - 9) );

      mpz_tdiv_q( temp, num, temp );

      number_group = mpz_get_ui( temp );

      if ( isPandigital( number_group ) )
      {
         mpz_clear( temp );
         mpz_clear( mod );

         return 1;
      }
   }

   mpz_clear( temp );
   mpz_clear( mod );

   return 0;
}

int main()
{
   mpz_t num1;
   mpz_init_set_str( num1, "1", 10 );

   mpz_t num2;
   mpz_init_set_str( num2, "1", 10 );

   char add_to_first = 1;
   char are_we_up_to_ten_digits = 0;
   int current_sequence = 2;

   while( 1 )
   {
      current_sequence++;

      if ( add_to_first )
      {
         mpz_add( num1, num1, num2 );
         add_to_first = 0;
      }
      else
      {
         mpz_add( num2, num1, num2 );
         add_to_first = 1;
      }

      if ( add_to_first )
      {
   //      printf( "\nNumber of digits: %d\n", numOfDigits( num2 ) );
         if ( areBothSidesPandigital( num2 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
      else
      {
         //printf( "\nNumber of digits: %d\n", numOfDigits( num1 ) );
         if ( areBothSidesPandigital( num1 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
   }

   //mpz_ui_pow_ui( temp, base, exp );

   //mpz_out_str( out_file, 10, temp );

   //printf("\n");
   //mpz_out_str( stdout, 10, temp );
   //printf("\n\n");

   printf("\n\n");

   return 0;
}

0 comments:

Post a Comment