Deceptive numbers: Difference between revisions

91 259 451 481 703 1729 2821 2981 3367 4141

4187 5461 6533 6541 6601 7471 7777 8149 8401 8911

10001 11111 12403 13981 14701 14911 15211 15841 19201 21931

22321 24013 24661 27613 29341 34133 34441 35113 38503 41041

45527 46657 48433 50851 50881 52633 54913 57181 63139 63973

65311 66991 67861 68101 75361 79003 82513 83119 94139 95161

97273 97681 100001 101101 101491 102173 108691 113201 115627 115921

118301 118957 122221 126217 128713 130351 131821 134821 134863 137137

137149 138481 139231 145181 147001 148417 152551 158497 162401 164761

166499 170017 172081 179881 188191 188269 188461 188501 196651 201917

</pre>

===Without external libraries==

<syntaxhighlight lang="c++">

#include <cmath>

#include <cstdint>

#include <iomanip>

#include <iostream>

uint64_t power_modulus(uint64_t base, uint64_t exponent, uint64_t modulus) {

if ( modulus == 1 ) {

return 0;

}

base %= modulus;

uint64_t result = 1;

while ( exponent > 0 ) {

if ( ( exponent & 1 ) == 1 ) {

result = ( result * base ) % modulus;

}

base = ( base * base ) % modulus;

exponent >>= 1;

}

return result;

}

bool is_deceptive(uint32_t n) {

if ( n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && power_modulus(10, n - 1, n) == 1 ) {

for ( uint32_t divisor = 7; divisor < sqrt(n); divisor += 6 ) {

if ( n % divisor == 0 || n % ( divisor + 4 ) == 0 ) {

return true;

}

}

}

return false;

}

int main() {

uint32_t n = 7;

uint32_t count = 0;

while ( count < 100 ) {

if ( is_deceptive(n) ) {

std::cout << std::setw(6) << n << ( ++count % 10 == 0 ? "\n" : " " );

}

n += 1;

}

}

</syntaxhighlight>

{{ out }}

<pre>