perfect number

        The number 131071 = 2^17 - 1 has two interesting properties:

        (1)  Its base-17 representation, (19b91)17, is palindromic (reading 
the same backward as forward).
        (2)  Its base-2 representation, (11111111111111111)2, has a run of 
at least 17 consecutive 1 bits.
        What is the next number with both of these properties?

因为要做OA， 网上看到之前有人说碰到过这题，搜了下答案，没人给过。我自己给了个解，放在这里，万一有人再要找，可以参考一下。晚上要做OA了，希望就是这题吧。。。lol

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134

#include <iostream> #include <climits> #include <string> using namespace std; /** * algorithm class to find the number with: * 1) base of 17 representation is palindrome * 2) base of 2 representation has 17 consective 1 bits */ class findNextPNumber { public: /** * @string input, input string representing a number using 17 as base * which has p form * @return unsigned long long, return the next 17 based palidoromed number * which has at least 17 consecutive 1 bits */ unsigned long long findNextPNumber17Bits(const string& input) { string cur = input; string next; while (1) { next = nextPNumber(cur); unsigned long long num = decode(next); if (num == ULLONG_MAX) // return 0; if (count_consecutive_ones(num) >= 17) { return num; } cur = next; } return 0; } private: /** * Test if an input string contains all 'G's (16) * if all is 'G', return true * else return false */ bool isAll16s(const string &num) { int n = num.size(); for (int i = 0; i < n; i++) { if (num[i] != 'g') return false; } return true; } ; /** * input a string with 17 as base and output * the value as 10 base */ unsigned long long decode(const string& in) { unsigned long long result = 0; int n = in.size(); for (int i = 0; i < n; i++) { if (isdigit(in[i])) result = result * 17 + in[i] - '0'; else result = result * 17 + (10 + in[i] - 'a'); } return result; } ; /** * count the maximum consecutive bits of 1s */ int count_consecutive_ones(unsigned long long input) { int count = 0; while (input) { input = (input & (input << 1)); count++; } return count; } /** * generate next p number */ string nextPNumber(const string& num) { if (isAll16s(num)) return '1' + string(num.size(), '0') + '1'; int n = num.size(); int mid = n / 2; int carry = 1; int i = mid - 1; int nums[n]; // decode of special chars for (int i = 0; i < n; i++) { if (isdigit(num[i])) nums[i] = num[i] - '0'; else nums[i] = 10 + num[i] - 'a'; } int j; // If there are odd digits, then increment // the middle digit and store the carry if (n % 2 == 1) { nums[mid] += carry; carry = nums[mid] / 17; nums[mid] %= 17; j = mid + 1; } else j = mid; // Add 1 to the rightmost digit of the left side, propagate the carry // towards MSB digit and simultaneously copying mirror of the left side // to the right side. while (i >= 0) { nums[i] += carry; carry = nums[i] / 17; nums[i] %= 17; nums[j++] = nums[i--]; // copy mirror to right } // encode to special chars string result; for (int i = 0; i < n; i++) { if (nums[i] < 10) result += (nums[i] + '0'); else result += (nums[i] - 10 + 'a'); } return result; } ; }; int main() { string cur = "19b91"; findNextPNumber solver; cout << solver.findNextPNumber17Bits(cur); return 0; }