Undulating numbers: Difference between revisions

</pre>

=={{header|C++}}==

<syntaxhighlight lang="cpp">#include <algorithm>

#include <cassert>

#include <cstdint>

#include <iomanip>

#include <iostream>

#include <vector>

bool is_prime(uint64_t n) {

if (n < 2)

return false;

if (n % 2 == 0)

return n == 2;

if (n % 3 == 0)

return n == 3;

for (uint64_t p = 5; p * p <= n; p += 4) {

if (n % p == 0)

return false;

p += 2;

if (n % p == 0)

return false;

}

return true;

}

class undulating_number_generator {

public:

explicit undulating_number_generator(int base) : base_(base) {}

uint64_t next() {

uint64_t n = 0;

for (int d = 0; d < digits_; ++d)

n = n * base_ + (d % 2 == 0 ? a_ : b_);

++b_;

if (a_ == b_)

++b_;

if (b_ == base_) {

++a_;

b_ = 0;

if (a_ == base_) {

a_ = 1;

++digits_;

}

}

return n;

}

private:

int base_;

int a_ = 1;

int b_ = 0;

int digits_ = 3;

};

std::string to_string(uint64_t n, int base) {

assert(base > 1 && base <= 16);

const char digits[] = "0123456789ABCDEF";

std::string str;

for (; n > 0; n /= base)

str += digits[n % base];

reverse(str.begin(), str.end());

return str;

}

void undulating(int base) {

undulating_number_generator gen(base);

uint64_t n = gen.next();

int i = 1;

uint64_t limit = base * base * base;

std::vector<uint64_t> primes;

std::cout << "3-digit undulating numbers in base " << base << ":\n";

for (; n < limit; ++i) {

std::cout << std::setw(3) << n << (i % 9 == 0 ? '\n' : ' ');

if (is_prime(n))

primes.push_back(n);

n = gen.next();

}

limit *= base;

std::cout << "\n4-digit undulating numbers in base " << base << ":\n";

for (; n < limit; ++i) {

std::cout << std::setw(4) << n << (i % 9 == 0 ? '\n' : ' ');

n = gen.next();

}

std::cout << "\n3-digit undulating numbers in base " << base

<< " which are prime:\n";

for (auto prime : primes)

std::cout << prime << ' ';

std::cout << '\n';

for (; i != 600; ++i)

n = gen.next();

std::cout << "\nThe 600th undulating number in base " << base << " is "

<< n;

if (base != 10) {

std::cout << "\nor expressed in base " << base << ": "

<< to_string(n, base);

}

std::cout << ".\n";

for (;; ++i) {

uint64_t next = gen.next();

if (next >= (1ULL << 53))

break;

n = next;

}

std::cout << "\nTotal number of undulating numbers < 2^53 in base " << base

<< ": " << i << "\nof which the largest is " << n;

if (base != 10) {

std::cout << "\nor expressed in base " << base << ": "

<< to_string(n, base);

}

std::cout << ".\n";

}

int main() {

undulating(10);

std::cout << '\n';

undulating(7);

}</syntaxhighlight>

{{out}}

<pre>

3-digit undulating numbers in base 10:

101 121 131 141 151 161 171 181 191

202 212 232 242 252 262 272 282 292

303 313 323 343 353 363 373 383 393

404 414 424 434 454 464 474 484 494

505 515 525 535 545 565 575 585 595

606 616 626 636 646 656 676 686 696

707 717 727 737 747 757 767 787 797

808 818 828 838 848 858 868 878 898

909 919 929 939 949 959 969 979 989

4-digit undulating numbers in base 10:

1010 1212 1313 1414 1515 1616 1717 1818 1919

2020 2121 2323 2424 2525 2626 2727 2828 2929

3030 3131 3232 3434 3535 3636 3737 3838 3939

4040 4141 4242 4343 4545 4646 4747 4848 4949

5050 5151 5252 5353 5454 5656 5757 5858 5959

6060 6161 6262 6363 6464 6565 6767 6868 6969

7070 7171 7272 7373 7474 7575 7676 7878 7979

8080 8181 8282 8383 8484 8585 8686 8787 8989

9090 9191 9292 9393 9494 9595 9696 9797 9898

3-digit undulating numbers in base 10 which are prime:

101 131 151 181 191 313 353 373 383 727 757 787 797 919 929

The 600th undulating number in base 10 is 4646464646.

Total number of undulating numbers < 2^53 in base 10: 1125

of which the largest is 8989898989898989.

3-digit undulating numbers in base 7:

50 64 71 78 85 92 100 107 121

128 135 142 150 157 164 178 185 192

200 207 214 221 235 242 250 257 264

271 278 292 300 307 314 321 328 335

4-digit undulating numbers in base 7:

350 450 500 550 600 650 700 750 850

900 950 1000 1050 1100 1150 1250 1300 1350

1400 1450 1500 1550 1650 1700 1750 1800 1850

1900 1950 2050 2100 2150 2200 2250 2300 2350

3-digit undulating numbers in base 7 which are prime:

71 107 157 257 271 307

The 600th undulating number in base 7 is 8074217422972642

or expressed in base 7: 4646464646464646464.

Total number of undulating numbers < 2^53 in base 7: 603

of which the largest is 8786648372058464

or expressed in base 7: 5252525252525252525.