All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Palindromic number counting (Posted on 2006-06-22)
Suppose you want to know how many palindromes are in the set of integers from 1 to N. Can you provide a formula for this? Otherwise, can you give an algorithm, as efficient as possible, to find the answer? And, are there special values of N for which there is a simple formula?

 No Solution Yet Submitted by Sir Percivale Rating: 3.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solved with C source code Comment 3 of 3 |
it's terribly written, but here is the C source code i wrote:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define FALSE 0
#define TRUE 1

// returns the digit in the 10^k's place
int getDigit(int num, int place) {
return (((num % (10 * place)) - (num % place)) / place);
}

// returns base^power
int power(int base, int power) {
for (int i = 0; i < power; i++) {
}
}

//returns the number of digits in a number
int getNumDigits (int num) {
int k = 0;
while(1) {
if ((num % power(10, k)) == num) {
return k;
}
k++;
}
return -1;
}

// returns whether a number is a palindrome
int isPalindrome(int num) {
int numDigits = getNumDigits(num);
for (int i = 0; i <= (numDigits / 2); i++) {
if (getDigit(num, power(10, i)) != getDigit(num, power(10, numDigits - 1 - i))) {
return FALSE;
}
}
return TRUE;
}

// return the next largest palindrome less than or equal to a number with the same length as that number
int nLP(int num) {
int lp = num;
int numDigits = getNumDigits(lp);
if (isPalindrome(lp) == 1) {
return lp;
}
if (getDigit(lp, pow(10, 0)) == 0) {
return nLP(lp - 1);
}
for (int i = 0; i <= (numDigits / 2); i++) {
lp -= (((getDigit(lp, power(10, i)) - getDigit(lp, power(10, numDigits - 1 - i))) + 10) % 10) * power(10, i);
if (isPalindrome(lp) == 1) {
return lp;
}
}
return 0;
}

// returns the number of palindromes less than a number with the same number of digits as that number
// there are 6*6*3 = 108 palindromes less than 65346 that have 5 digits (biggest = 65256)
// there are 9*10*10 = 900 palindromes less than 999999 that have 6 digits
int numPalies(num) {
int lp = nLP(num);
int numDigits = getNumDigits(lp);
for (int i = 1; i < (int)ceil((double)((double)numDigits / 2)); i++) {
answer *= (getDigit(lp, power(10, i)) + 1);
}
}

void main() {
int num, numDigits;
printf("Enter an integer: ");
while (scanf("%d", &num) == 0) {
printf("ERROR: Not An Integer\n");
break;
}
numDigits = getNumDigits(nLP(num));
printf("number of palindromes with %d digits less than or equal to %d is %d\n", numDigits, num, numPalies(num));
for (int i = numDigits - 1; i > 0; i--) {
printf("number of palindromes with %d digits less than or equal to %d is %d\n", i, power(10, i), numPalies(power(10, i) - 1));
}
for (int i = numDigits - 1; i > 0; i--) {
answer += numPalies(power(10, i) - 1);
}
printf("total number of palindromes less than or equal to %d is %d", num, answer);
}

 Posted by cheesesteak on 2006-06-23 23:21:02

 Search: Search body:
Forums (0)