//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;
}
Sunday, April 4, 2010
Solution - #104 Project Euler
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment