Achilles numbers: Difference between revisions

</pre>

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

{{trans|Wren}}

{{libheader|Boost}}

<lang cpp>#include <algorithm>

#include <chrono>

#include <cmath>

#include <cstdint>

#include <iomanip>

#include <iostream>

#include <vector>

#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::uint128_t;

template <typename T> void unique_sort(std::vector<T>& vector) {

std::sort(vector.begin(), vector.end());

vector.erase(std::unique(vector.begin(), vector.end()), vector.end());

}

auto perfect_powers(uint128_t n) {

std::vector<uint128_t> result;

for (uint128_t i = 2, s = sqrt(n); i <= s; ++i)

for (uint128_t p = i * i; p < n; p *= i)

result.push_back(p);

unique_sort(result);

return result;

}

auto achilles(uint128_t from, uint128_t to, const std::vector<uint128_t>& pps) {

std::vector<uint128_t> result;

auto c = static_cast<uint128_t>(std::cbrt(static_cast<double>(to / 4)));

auto s = sqrt(to / 8);

for (uint128_t b = 2; b <= c; ++b) {

uint128_t b3 = b * b * b;

for (uint128_t a = 2; a <= s; ++a) {

uint128_t p = b3 * a * a;

if (p >= to)

break;

if (p >= from && !binary_search(pps.begin(), pps.end(), p))

result.push_back(p);

}

}

unique_sort(result);

return result;

}

uint128_t totient(uint128_t n) {

uint128_t tot = n;

if ((n & 1) == 0) {

while ((n & 1) == 0)

n >>= 1;

tot -= tot >> 1;

}

for (uint128_t p = 3; p * p <= n; p += 2) {

if (n % p == 0) {

while (n % p == 0)

n /= p;

tot -= tot / p;

}

}

if (n > 1)

tot -= tot / n;

return tot;

}

int main() {

auto start = std::chrono::high_resolution_clock::now();

const uint128_t limit = 1000000000000000;

auto pps = perfect_powers(limit);

auto ach = achilles(1, 1000000, pps);

std::cout << "First 50 Achilles numbers:\n";

for (size_t i = 0; i < 50 && i < ach.size(); ++i)

std::cout << std::setw(4) << ach[i] << ((i + 1) % 10 == 0 ? '\n' : ' ');

std::cout << "\nFirst 50 strong Achilles numbers:\n";

for (size_t i = 0, count = 0; count < 50 && i < ach.size(); ++i)

if (binary_search(ach.begin(), ach.end(), totient(ach[i])))

std::cout << std::setw(6) << ach[i]

<< (++count % 10 == 0 ? '\n' : ' ');

int digits = 2;

std::cout << "\nNumber of Achilles numbers with:\n";

for (uint128_t from = 1, to = 100; to <= limit; to *= 10, ++digits) {

size_t count = achilles(from, to, pps).size();

std::cout << std::setw(2) << digits << " digits: " << count << '\n';

from = to;

}

auto end = std::chrono::high_resolution_clock::now();

std::chrono::duration<double> duration(end - start);

std::cout << "\nElapsed time: " << duration.count() << " seconds\n";

}</lang>

{{out}}

<pre>

First 50 Achilles numbers:

72 108 200 288 392 432 500 648 675 800

864 968 972 1125 1152 1323 1352 1372 1568 1800

1944 2000 2312 2592 2700 2888 3087 3200 3267 3456

3528 3872 3888 4000 4232 4500 4563 4608 5000 5292

5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 50 strong Achilles numbers:

500 864 1944 2000 2592 3456 5000 10125 10368 12348

12500 16875 19652 19773 30375 31104 32000 33275 37044 40500

49392 50000 52488 55296 61731 64827 67500 69984 78608 80000

81000 83349 84375 93312 108000 111132 124416 128000 135000 148176

151875 158184 162000 165888 172872 177957 197568 200000 202612 209952

Number of Achilles numbers with:

2 digits: 1

3 digits: 12

4 digits: 47

5 digits: 192

6 digits: 664

7 digits: 2242

8 digits: 7395

9 digits: 24008

10 digits: 77330

11 digits: 247449

12 digits: 788855

13 digits: 2508051

14 digits: 7960336

15 digits: 25235383

Elapsed time: 13.2644 seconds

</pre>

=={{header|Rust}}==

{{trans|Wren}}

<lang rust>fn perfect_powers(n: u128) -> Vec<u128> {

let mut powers = Vec::<u128>::new();

let sqrt = (n as f64).sqrt() as u128;

for i in 2..=sqrt {

let mut p = i * i;

while p < n {

powers.push(p);

p *= i;

}

}

powers.sort();

powers.dedup();

powers

}

fn bsearch<T: Ord>(vector: &Vec<T>, value: &T) -> bool {

match vector.binary_search(value) {

Ok(_) => true,

_ => false,

}

}

fn achilles(from: u128, to: u128, pps: &Vec<u128>) -> Vec<u128> {

let mut result = Vec::<u128>::new();

let cbrt = ((to / 4) as f64).cbrt() as u128;

let sqrt = ((to / 8) as f64).sqrt() as u128;

for b in 2..=cbrt {

let b3 = b * b * b;

for a in 2..=sqrt {

let p = b3 * a * a;

if p >= to {

break;

}

if p >= from && !bsearch(&pps, &p) {

result.push(p);

}

}

}

result.sort();

result.dedup();

result

}

fn totient(mut n: u128) -> u128 {

let mut tot = n;

if (n & 1) == 0 {

while (n & 1) == 0 {

n >>= 1;

}

tot -= tot >> 1;

}

let mut p = 3;

while p * p <= n {

if n % p == 0 {

while n % p == 0 {

n /= p;

}

tot -= tot / p;

}

p += 2;

}

if n > 1 {

tot -= tot / n;

}

tot

}

fn main() {

use std::time::Instant;

let t0 = Instant::now();

let limit = 1000000000000000u128;

let pps = perfect_powers(limit);

let ach = achilles(1, 1000000, &pps);

println!("First 50 Achilles numbers:");

for i in 0..50 {

print!("{:4}{}", ach[i], if (i + 1) % 10 == 0 { "\n" } else { " " });

}

println!("\nFirst 50 strong Achilles numbers:");

for (i, n) in ach

.iter()

.filter(|&x| bsearch(&ach, &totient(*x)))

.take(50)

.enumerate()

{

print!("{:6}{}", n, if (i + 1) % 10 == 0 { "\n" } else { " " });

}

println!();

let mut from = 1u128;

let mut to = 100u128;

let mut digits = 2;

while to <= limit {

let count = achilles(from, to, &pps).len();

println!("{:2} digits: {}", digits, count);

from = to;

to *= 10;

digits += 1;

}

let duration = t0.elapsed();

println!("\nElapsed time: {} milliseconds", duration.as_millis());

}</lang>

{{out}}

<pre>

First 50 Achilles numbers:

72 108 200 288 392 432 500 648 675 800

864 968 972 1125 1152 1323 1352 1372 1568 1800

1944 2000 2312 2592 2700 2888 3087 3200 3267 3456

3528 3872 3888 4000 4232 4500 4563 4608 5000 5292

5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 50 strong Achilles numbers:

500 864 1944 2000 2592 3456 5000 10125 10368 12348

12500 16875 19652 19773 30375 31104 32000 33275 37044 40500

49392 50000 52488 55296 61731 64827 67500 69984 78608 80000

81000 83349 84375 93312 108000 111132 124416 128000 135000 148176

151875 158184 162000 165888 172872 177957 197568 200000 202612 209952

2 digits: 1

3 digits: 12

4 digits: 47

5 digits: 192

6 digits: 664

7 digits: 2242

8 digits: 7395

9 digits: 24008

10 digits: 77330

11 digits: 247449

12 digits: 788855

13 digits: 2508051

14 digits: 7960336

15 digits: 25235383

Elapsed time: 12608 milliseconds