N-smooth numbers
You are encouraged to solve this task according to the task description, using any language you may know.
n-smooth numbers are positive integers which have no prime factors > n.
The n (when using it in the expression) n-smooth is always prime,
there are no 9-smooth numbers.
1 (unity) is always included in n-smooth numbers.
2-smooth numbers are non-negative powers of two.
5-smooth numbers are also called Hamming numbers.
7-smooth numbers are also called humble numbers.
A way to express 11-smooth numbers is:
11-smooth = 2i × 3j × 5k × 7m × 11p
where i, j, k, m, p ≥ 0
- Task
-
- calculate and show the first 25 n-smooth numbers for n=2 ───► n=29
- calculate and show three numbers starting with 3,000 n-smooth numbers for n=3 ───► n=29
- calculate and show twenty numbers starting with 30,000 n-smooth numbers for n=503 ───► n=521 (optional)
All ranges (for n) are to be inclusive, and only prime numbers are to be used.
The (optional) n-smooth numbers for the third range are: 503, 509, and 521.
Show all n-smooth numbers for any particular n in a horizontal list.
Show all output here on this page.
- Related tasks
- References
-
- Wikipedia entry: Hamming numbers (this link is re-directed to Regular number).
- Wikipedia entry: Smooth number
- OEIS entry: A000079 2-smooth numbers or non-negative powers of two
- OEIS entry: A003586 3-smooth numbers
- OEIS entry: A051037 5-smooth numbers or Hamming numbers
- OEIS entry: A002473 7-smooth numbers or humble numbers
- OEIS entry: A051038 11-smooth numbers
- OEIS entry: A080197 13-smooth numbers
- OEIS entry: A080681 17-smooth numbers
- OEIS entry: A080682 19-smooth numbers
- OEIS entry: A080683 23-smooth numbers
11l
V primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
F isPrime(n)
I n < 2
R 0B
L(i) :primes
I n == i
R 1B
I n % i == 0
R 0B
I i * i > n
R 1B
print(‘Oops, ’n‘ is too large’)
R 0B
F init()
V s = 24
L s < 600
I isPrime(s - 1) & s - 1 > :primes.last
:primes.append(s - 1)
I isPrime(s + 1) & s + 1 > :primes.last
:primes.append(s + 1)
s += 6
F nsmooth(n, size)
assert(n C 2..521)
assert(size >= 1)
V bn = n
V ok = 0B
L(prime) :primes
I bn == prime
ok = 1B
L.break
assert(ok, ‘must be a prime number’)
V ns = [BigInt(0)] * size
ns[0] = 1
[BigInt] next
L(prime) :primes
I prime > bn
L.break
next.append(prime)
V indicies = [0] * next.len
L(m) 1 .< size
ns[m] = min(next)
L(i) 0 .< indicies.len
I ns[m] == next[i]
indicies[i]++
next[i] = :primes[i] * ns[indicies[i]]
R ns
init()
L(p) primes
I p >= 30
L.break
print(‘The first ’p‘ -smooth numbers are:’)
print(nsmooth(p, 25))
print()
L(p) primes[1..]
I p >= 30
L.break
print(‘The 3000 to 3202 ’p‘ -smooth numbers are:’)
print(nsmooth(p, 3002)[2999..])
print()
L(p) [503, 509, 521]
print(‘The 30000 to 3019 ’p‘ -smooth numbers are:’)
print(nsmooth(p, 30019)[29999..])
print()- Output:
The first 2 -smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 3 -smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 5 -smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 7 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 11 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 13 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 17 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 19 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 23 -smooth numbers are: [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] The first 29 -smooth numbers are: [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] The 3000 to 3202 3 -smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3000 to 3202 5 -smooth numbers are: [278942752080, 279936000000, 281250000000] The 3000 to 3202 7 -smooth numbers are: [50176000, 50331648, 50388480] The 3000 to 3202 11 -smooth numbers are: [2112880, 2116800, 2117016] The 3000 to 3202 13 -smooth numbers are: [390000, 390390, 390625] The 3000 to 3202 17 -smooth numbers are: [145800, 145860, 146016] The 3000 to 3202 19 -smooth numbers are: [74256, 74358, 74360] The 3000 to 3202 23 -smooth numbers are: [46552, 46575, 46585] The 3000 to 3202 29 -smooth numbers are: [33516, 33524, 33534] The 30000 to 3019 503 -smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30000 to 3019 509 -smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30000 to 3019 521 -smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
C
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
void* xmalloc(size_t n) {
void* ptr = malloc(n);
if (ptr == NULL) {
fprintf(stderr, "Out of memory\n");
exit(1);
}
return ptr;
}
void* xrealloc(void* p, size_t n) {
void* ptr = realloc(p, n);
if (ptr == NULL) {
fprintf(stderr, "Out of memory\n");
exit(1);
}
return ptr;
}
bool is_prime(uint32_t n) {
if (n == 2)
return true;
if (n < 2 || n % 2 == 0)
return false;
for (uint32_t p = 3; p * p <= n; p += 2) {
if (n % p == 0)
return false;
}
return true;
}
// Populates primes with the prime numbers between from and to and
// returns the number of primes found.
uint32_t find_primes(uint32_t from, uint32_t to, uint32_t** primes) {
uint32_t count = 0, buffer_length = 16;
uint32_t* buffer = xmalloc(sizeof(uint32_t) * buffer_length);
for (uint32_t p = from; p <= to; ++p) {
if (is_prime(p)) {
if (count >= buffer_length) {
uint32_t new_length = buffer_length * 2;
if (new_length < count + 1)
new_length = count + 1;
buffer = xrealloc(buffer, sizeof(uint32_t) * new_length);
buffer_length = new_length;
}
buffer[count++] = p;
}
}
*primes = buffer;
return count;
}
void free_numbers(mpz_t* numbers, size_t count) {
for (size_t i = 0; i < count; ++i)
mpz_clear(numbers[i]);
free(numbers);
}
// Returns an array containing first count n-smooth numbers
mpz_t* find_nsmooth_numbers(uint32_t n, uint32_t count) {
uint32_t* primes = NULL;
uint32_t num_primes = find_primes(2, n, &primes);
mpz_t* numbers = xmalloc(sizeof(mpz_t) * count);
mpz_t* queue = xmalloc(sizeof(mpz_t) * num_primes);
uint32_t* index = xmalloc(sizeof(uint32_t) * num_primes);
for (uint32_t i = 0; i < num_primes; ++i) {
index[i] = 0;
mpz_init_set_ui(queue[i], primes[i]);
}
for (uint32_t i = 0; i < count; ++i)
mpz_init(numbers[i]);
mpz_set_ui(numbers[0], 1);
for (uint32_t i = 1; i < count; ++i) {
for (uint32_t p = 0; p < num_primes; ++p) {
if (mpz_cmp(queue[p], numbers[i - 1]) == 0)
mpz_mul_ui(queue[p], numbers[++index[p]], primes[p]);
}
uint32_t min_index = 0;
for (uint32_t p = 1; p < num_primes; ++p) {
if (mpz_cmp(queue[min_index], queue[p]) > 0)
min_index = p;
}
mpz_set(numbers[i], queue[min_index]);
}
free_numbers(queue, num_primes);
free(primes);
free(index);
return numbers;
}
void print_nsmooth_numbers(uint32_t n, uint32_t begin, uint32_t count) {
uint32_t num = begin + count;
mpz_t* numbers = find_nsmooth_numbers(n, num);
printf("%u: ", n);
mpz_out_str(stdout, 10, numbers[begin]);
for (uint32_t i = 1; i < count; ++i) {
printf(", ");
mpz_out_str(stdout, 10, numbers[begin + i]);
}
printf("\n");
free_numbers(numbers, num);
}
int main() {
printf("First 25 n-smooth numbers for n = 2 -> 29:\n");
for (uint32_t n = 2; n <= 29; ++n) {
if (is_prime(n))
print_nsmooth_numbers(n, 0, 25);
}
printf("\n3 n-smooth numbers starting from 3000th for n = 3 -> 29:\n");
for (uint32_t n = 3; n <= 29; ++n) {
if (is_prime(n))
print_nsmooth_numbers(n, 2999, 3);
}
printf("\n20 n-smooth numbers starting from 30,000th for n = 503 -> 521:\n");
for (uint32_t n = 503; n <= 521; ++n) {
if (is_prime(n))
print_nsmooth_numbers(n, 29999, 20);
}
return 0;
}
- Output:
First 25 n-smooth numbers for n = 2 -> 29: 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216 3: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192 5: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54 7: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36 11: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32 13: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28 17: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27 19: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26 23: 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 29: 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 3 n-smooth numbers starting from 3000th for n = 3 -> 29: 3: 91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928 5: 278942752080, 279936000000, 281250000000 7: 50176000, 50331648, 50388480 11: 2112880, 2116800, 2117016 13: 390000, 390390, 390625 17: 145800, 145860, 146016 19: 74256, 74358, 74360 23: 46552, 46575, 46585 29: 33516, 33524, 33534 20 n-smooth numbers starting from 30,000th for n = 503 -> 521: 503: 62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964 509: 62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646 521: 62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336
C++
The output for the 30,000 3-smooth numbers is not correct due to insuffiant bits to represent that actual value
#include <algorithm>
#include <iostream>
#include <vector>
std::vector<uint64_t> primes;
std::vector<uint64_t> smallPrimes;
template <typename T>
std::ostream &operator <<(std::ostream &os, const std::vector<T> &v) {
auto it = v.cbegin();
auto end = v.cend();
os << '[';
if (it != end) {
os << *it;
it = std::next(it);
}
for (; it != end; it = std::next(it)) {
os << ", " << *it;
}
return os << ']';
}
bool isPrime(uint64_t value) {
if (value < 2) return false;
if (value % 2 == 0) return value == 2;
if (value % 3 == 0) return value == 3;
if (value % 5 == 0) return value == 5;
if (value % 7 == 0) return value == 7;
if (value % 11 == 0) return value == 11;
if (value % 13 == 0) return value == 13;
if (value % 17 == 0) return value == 17;
if (value % 19 == 0) return value == 19;
if (value % 23 == 0) return value == 23;
uint64_t t = 29;
while (t * t < value) {
if (value % t == 0) return false;
value += 2;
if (value % t == 0) return false;
value += 4;
}
return true;
}
void init() {
primes.push_back(2);
smallPrimes.push_back(2);
uint64_t i = 3;
while (i <= 521) {
if (isPrime(i)) {
primes.push_back(i);
if (i <= 29) {
smallPrimes.push_back(i);
}
}
i += 2;
}
}
std::vector<uint64_t> nSmooth(uint64_t n, size_t size) {
if (n < 2 || n>521) {
throw std::runtime_error("n must be between 2 and 521");
}
if (size <= 1) {
throw std::runtime_error("size must be at least 1");
}
uint64_t bn = n;
if (primes.cend() == std::find(primes.cbegin(), primes.cend(), bn)) {
throw std::runtime_error("n must be a prime number");
}
std::vector<uint64_t> ns(size, 0);
ns[0] = 1;
std::vector<uint64_t> next;
for (auto prime : primes) {
if (prime > bn) {
break;
}
next.push_back(prime);
}
std::vector<size_t> indicies(next.size(), 0);
for (size_t m = 1; m < size; m++) {
ns[m] = *std::min_element(next.cbegin(), next.cend());
for (size_t i = 0; i < indicies.size(); i++) {
if (ns[m] == next[i]) {
indicies[i]++;
next[i] = primes[i] * ns[indicies[i]];
}
}
}
return ns;
}
int main() {
init();
for (auto i : smallPrimes) {
std::cout << "The first " << i << "-smooth numbers are:\n";
std::cout << nSmooth(i, 25) << '\n';
std::cout << '\n';
}
// there is not enough bits to fully represent the 3-smooth numbers
for (size_t i = 0; i < smallPrimes.size(); i++) {
if (i < 1) continue;
auto p = smallPrimes[i];
auto v = nSmooth(p, 3002);
v.erase(v.begin(), v.begin() + 2999);
std::cout << "The 30,000th to 30,019th " << p << "-smooth numbers are:\n";
std::cout << v << '\n';
std::cout << '\n';
}
return 0;
}
- Output:
The first 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 23-smooth numbers are: [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] The first 29-smooth numbers are: [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] The 30,000th to 30,019th 3-smooth numbers are: [15283969189597937664, 12248739612010217472, 0] The 30,000th to 30,019th 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 30,000th to 30,019th 7-smooth numbers are: [50176000, 50331648, 50388480] The 30,000th to 30,019th 11-smooth numbers are: [2112880, 2116800, 2117016] The 30,000th to 30,019th 13-smooth numbers are: [390000, 390390, 390625] The 30,000th to 30,019th 17-smooth numbers are: [145800, 145860, 146016] The 30,000th to 30,019th 19-smooth numbers are: [74256, 74358, 74360] The 30,000th to 30,019th 23-smooth numbers are: [46552, 46575, 46585] The 30,000th to 30,019th 29-smooth numbers are: [33516, 33524, 33534]
C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace NSmooth {
class Program {
static readonly List<BigInteger> primes = new List<BigInteger>();
static readonly List<int> smallPrimes = new List<int>();
static Program() {
primes.Add(2);
smallPrimes.Add(2);
BigInteger i = 3;
while (i <= 521) {
if (IsPrime(i)) {
primes.Add(i);
if (i <= 29) {
smallPrimes.Add((int)i);
}
}
i += 2;
}
}
static bool IsPrime(BigInteger value) {
if (value < 2) return false;
if (value % 2 == 0) return value == 2;
if (value % 3 == 0) return value == 3;
if (value % 5 == 0) return value == 5;
if (value % 7 == 0) return value == 7;
if (value % 11 == 0) return value == 11;
if (value % 13 == 0) return value == 13;
if (value % 17 == 0) return value == 17;
if (value % 19 == 0) return value == 19;
if (value % 23 == 0) return value == 23;
BigInteger t = 29;
while (t * t < value) {
if (value % t == 0) return false;
value += 2;
if (value % t == 0) return false;
value += 4;
}
return true;
}
static List<BigInteger> NSmooth(int n, int size) {
if (n < 2 || n > 521) {
throw new ArgumentOutOfRangeException("n");
}
if (size < 1) {
throw new ArgumentOutOfRangeException("size");
}
BigInteger bn = n;
bool ok = false;
foreach (var prime in primes) {
if (bn == prime) {
ok = true;
break;
}
}
if (!ok) {
throw new ArgumentException("must be a prime number", "n");
}
BigInteger[] ns = new BigInteger[size];
ns[0] = 1;
for (int i = 1; i < size; i++) {
ns[i] = 0;
}
List<BigInteger> next = new List<BigInteger>();
foreach (var prime in primes) {
if (prime > bn) {
break;
}
next.Add(prime);
}
int[] indices = new int[next.Count];
for (int i = 0; i < indices.Length; i++) {
indices[i] = 0;
}
for (int m = 1; m < size; m++) {
ns[m] = next.Min();
for (int i = 0; i < indices.Length; i++) {
if (ns[m] == next[i]) {
indices[i]++;
next[i] = primes[i] * ns[indices[i]];
}
}
}
return ns.ToList();
}
static void Println<T>(IEnumerable<T> nums) {
Console.Write('[');
var it = nums.GetEnumerator();
if (it.MoveNext()) {
Console.Write(it.Current);
}
while (it.MoveNext()) {
Console.Write(", ");
Console.Write(it.Current);
}
Console.WriteLine(']');
}
static void Main() {
foreach (var i in smallPrimes) {
Console.WriteLine("The first {0}-smooth numbers are:", i);
Println(NSmooth(i, 25));
Console.WriteLine();
}
foreach (var i in smallPrimes.Skip(1)) {
Console.WriteLine("The 3,000 to 3,202 {0}-smooth numbers are:", i);
Println(NSmooth(i, 3_002).Skip(2_999));
Console.WriteLine();
}
foreach (var i in new int[] { 503, 509, 521 }) {
Console.WriteLine("The 30,000 to 3,019 {0}-smooth numbers are:", i);
Println(NSmooth(i, 30_019).Skip(29_999));
Console.WriteLine();
}
}
}
}
- Output:
The first 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 23-smooth numbers are: [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] The first 29-smooth numbers are: [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] The 3,000 to 3,202 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3,000 to 3,202 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3,000 to 3,202 7-smooth numbers are: [50176000, 50331648, 50388480] The 3,000 to 3,202 11-smooth numbers are: [2112880, 2116800, 2117016] The 3,000 to 3,202 13-smooth numbers are: [390000, 390390, 390625] The 3,000 to 3,202 17-smooth numbers are: [145800, 145860, 146016] The 3,000 to 3,202 19-smooth numbers are: [74256, 74358, 74360] The 3,000 to 3,202 23-smooth numbers are: [46552, 46575, 46585] The 3,000 to 3,202 29-smooth numbers are: [33516, 33524, 33534] The 30,000 to 3,019 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000 to 3,019 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000 to 3,019 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Crystal
require "big"
def prime?(n) # P3 Prime Generator primality test
return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5
sqrt_n = Math.isqrt(n) # For Crystal < 1.2.0 use Math.sqrt(n).to_i
pc = typeof(n).new(5)
while pc <= sqrt_n
return false if n % pc == 0 || n % (pc + 2) == 0
pc += 6
end
true
end
def gen_primes(a, b)
(a..b).select { |pc| pc if prime? pc }
end
def nsmooth(n, limit)
raise "Exception(n or limit)" if n < 2 || n > 521 || limit < 1
raise "Exception(must be a prime number: n)" unless prime? n
primes = gen_primes(2, n)
ns = [0.to_big_i] * limit
ns[0] = 1.to_big_i
nextp = primes[0..primes.index(n)].map { |prm| prm.to_big_i }
indices = [0] * nextp.size
(1...limit).each do |m|
ns[m] = nextp.min
(0...indices.size).each do |i|
if ns[m] == nextp[i]
indices[i] += 1
nextp[i] = primes[i] * ns[indices[i]]
end
end
end
ns
end
gen_primes(2, 29).each do |prime|
print "The first 25 #{prime}-smooth numbers are: \n"
print nsmooth(prime, 25)
puts
end
puts
gen_primes(3, 29).each do |prime|
print "The 3000 to 3202 #{prime}-smooth numbers are: "
print nsmooth(prime, 3002)[2999..]
puts
end
puts
gen_primes(503, 521).each do |prime|
print "The 30,000 to 30,019 #{prime}-smooth numbers are: \n"
print nsmooth(prime, 30019)[29999..]
puts
end
- Output:
The first 25 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 25 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 25 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 25 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 25 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 25 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 25 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 25 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 25 23-smooth numbers are: [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] The first 25 29-smooth numbers are: [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] The 3000 to 3002 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3000 to 3002 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3000 to 3002 7-smooth numbers are: [50176000, 50331648, 50388480] The 3000 to 3002 11-smooth numbers are: [2112880, 2116800, 2117016] The 3000 to 3002 13-smooth numbers are: [390000, 390390, 390625] The 3000 to 3002 17-smooth numbers are: [145800, 145860, 146016] The 3000 to 3002 19-smooth numbers are: [74256, 74358, 74360] The 3000 to 3002 23-smooth numbers are: [46552, 46575, 46585] The 3000 to 3002 29-smooth numbers are: [33516, 33524, 33534] The 30,000 to 30,019 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000 to 30,019 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000 to 30,019 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
D
import std.algorithm;
import std.bigint;
import std.exception;
import std.range;
import std.stdio;
BigInt[] primes;
int[] smallPrimes;
bool isPrime(BigInt value) {
if (value < 2) return false;
if (value % 2 == 0) return value == 2;
if (value % 3 == 0) return value == 3;
if (value % 5 == 0) return value == 5;
if (value % 7 == 0) return value == 7;
if (value % 11 == 0) return value == 11;
if (value % 13 == 0) return value == 13;
if (value % 17 == 0) return value == 17;
if (value % 19 == 0) return value == 19;
if (value % 23 == 0) return value == 23;
BigInt t = 29;
while (t * t < value) {
if (value % t == 0) return false;
value += 2;
if (value % t == 0) return false;
value += 4;
}
return true;
}
// cache all primes up to 521
void init() {
primes ~= BigInt(2);
smallPrimes ~= 2;
BigInt i = 3;
while (i <= 521) {
if (isPrime(i)) {
primes ~= i;
if (i <= 29) {
smallPrimes ~= i.toInt;
}
}
i += 2;
}
}
BigInt[] nSmooth(int n, int size)
in {
enforce(n >= 2 && n <= 521, "n must be between 2 and 521");
enforce(size > 1, "size must be at least 1");
}
do {
BigInt bn = n;
bool ok = false;
foreach (prime; primes) {
if (bn == prime) {
ok = true;
break;
}
}
enforce(ok, "n must be a prime number");
BigInt[] ns;
ns.length = size;
ns[] = BigInt(0);
ns[0] = 1;
BigInt[] next;
foreach(prime; primes) {
if (prime > bn) {
break;
}
next ~= prime;
}
int[] indicies;
indicies.length = next.length;
indicies[] = 0;
foreach (m; 1 .. size) {
ns[m] = next.reduce!min;
foreach (i,v; indicies) {
if (ns[m] == next[i]) {
indicies[i]++;
next[i] = primes[i] * ns[indicies[i]];
}
}
}
return ns;
}
void main() {
init();
foreach (i; smallPrimes) {
writeln("The first ", i, "-smooth numbers are:");
writeln(nSmooth(i, 25));
writeln;
}
foreach (i; smallPrimes.drop(1)) {
writeln("The 3,000th to 3,202 ", i, "-smooth numbers are:");
writeln(nSmooth(i, 3_002).drop(2_999));
writeln;
}
foreach (i; [503, 509, 521]) {
writeln("The 30,000th to 30,019 ", i, "-smooth numbers are:");
writeln(nSmooth(i, 30_019).drop(29_999));
writeln;
}
}
- Output:
The first 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 23-smooth numbers are: [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] The first 29-smooth numbers are: [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] The 3,000th to 3,202 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3,000th to 3,202 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3,000th to 3,202 7-smooth numbers are: [50176000, 50331648, 50388480] The 3,000th to 3,202 11-smooth numbers are: [2112880, 2116800, 2117016] The 3,000th to 3,202 13-smooth numbers are: [390000, 390390, 390625] The 3,000th to 3,202 17-smooth numbers are: [145800, 145860, 146016] The 3,000th to 3,202 19-smooth numbers are: [74256, 74358, 74360] The 3,000th to 3,202 23-smooth numbers are: [46552, 46575, 46585] The 3,000th to 3,202 29-smooth numbers are: [33516, 33524, 33534] The 30,000th to 30,019 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000th to 30,019 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000th to 30,019 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Delphi
Thanks for Rudy Velthuis[1]
program N_smooth_numbers;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils,
System.Generics.Collections,
Velthuis.BigIntegers;
var
primes: TList<BigInteger>;
smallPrimes: TList<Integer>;
function IsPrime(value: BigInteger): Boolean;
var
v: BigInteger;
begin
if value < 2 then
exit(False);
for v in [2, 3, 5, 7, 11, 13, 17, 19, 23] do
begin
if (value mod v) = 0 then
exit(value = v);
end;
v := 29;
while v * v < value do
begin
if (value mod v) = 0 then
exit(False);
inc(value, 2);
if (value mod v) = 0 then
exit(False);
inc(v, 4);
end;
Result := True;
end;
function Min(values: TList<BigInteger>): BigInteger;
var
value: BigInteger;
begin
if values.Count = 0 then
exit(0);
Result := values[0];
for value in values do
begin
if value < Result then
result := value;
end;
end;
function NSmooth(n, size: Integer): TList<BigInteger>;
var
bn, p: BigInteger;
ok: Boolean;
i: Integer;
next: TList<BigInteger>;
indices: TList<Integer>;
m: Integer;
begin
Result := TList<BigInteger>.Create;
if (n < 2) or (n > 521) then
raise Exception.Create('Argument out of range: "n"');
if (size < 1) then
raise Exception.Create('Argument out of range: "size"');
bn := n;
ok := false;
for p in primes do
begin
ok := bn = p;
if ok then
break;
end;
if not ok then
raise Exception.Create('"n" must be a prime number');
Result.Add(1);
for i := 1 to size - 1 do
Result.Add(0);
next := TList<BigInteger>.Create;
for p in primes do
begin
if p > bn then
Break;
next.Add(p);
end;
indices := TList<Integer>.Create;
for i := 0 to next.Count - 1 do
indices.Add(0);
for m := 1 to size - 1 do
begin
Result[m] := Min(next);
for i := 0 to indices.Count - 1 do
if Result[m] = next[i] then
begin
indices[i] := indices[i] + 1;
next[i] := primes[i] * Result[indices[i]];
end;
end;
indices.Free;
next.Free;
end;
procedure Init();
var
i: BigInteger;
begin
primes := TList<BigInteger>.Create;
smallPrimes := TList<Integer>.Create;
primes.Add(2);
smallPrimes.Add(2);
i := 3;
while i <= 521 do
begin
if IsPrime(i) then
begin
primes.Add(i);
if i <= 29 then
smallPrimes.Add(Integer(i));
end;
inc(i, 2);
end;
end;
procedure Println(values: TList<BigInteger>; CanFree: Boolean = False);
var
value: BigInteger;
begin
Write('[');
for value in values do
Write(value.ToString, ', ');
Writeln(']'#10);
if CanFree then
values.Free;
end;
procedure Finish();
begin
primes.Free;
smallPrimes.Free;
end;
var
p: Integer;
ns: TList<BigInteger>;
const
RANGE_3: array[0..2] of integer = (503, 509, 521);
begin
Init;
for p in smallPrimes do
begin
Writeln('The first ', p, '-smooth numbers are:');
Println(NSmooth(p, 25), True);
end;
smallPrimes.Delete(0);
for p in smallPrimes do
begin
Writeln('The 3,000 to 3,202 ', p, '-smooth numbers are:');
ns := nSmooth(p, 3002);
ns.DeleteRange(0, 2999);
println(ns, True);
end;
for p in RANGE_3 do
begin
Writeln('The 3,000 to 3,019 ', p, '-smooth numbers are:');
ns := nSmooth(p, 30019);
ns.DeleteRange(0, 29999);
println(ns, True);
end;
Finish;
Readln;
end.
Factor
USING: deques dlists formatting fry io kernel locals make math
math.order math.primes math.text.english namespaces prettyprint
sequences tools.memory.private ;
IN: rosetta-code.n-smooth-numbers
SYMBOL: primes
: ns ( n -- seq )
primes-upto [ primes set ] [ length [ 1 1dlist ] replicate ]
bi ;
: enqueue ( n seq -- )
[ primes get ] 2dip [ '[ _ * ] map ] dip [ push-back ] 2each
;
: next ( seq -- n )
dup [ peek-front ] map infimum
[ '[ dup peek-front _ = [ pop-front* ] [ drop ] if ] each ]
[ swap enqueue ] [ nip ] 2tri ;
: next-n ( seq n -- seq )
swap '[ _ [ _ next , ] times ] { } make ;
:: n-smooth ( n from to -- seq )
n ns to next-n to from - 1 + tail* ;
:: show-smooth ( plo phi lo hi -- )
plo phi primes-between [
:> p lo commas lo ordinal-suffix hi commas hi
ordinal-suffix p "%s%s through %s%s %d-smooth numbers: "
printf p lo hi n-smooth [ pprint bl ] each nl
] each ;
: smooth-numbers-demo ( -- )
2 29 1 25 show-smooth nl
3 29 3000 3002 show-smooth nl
503 521 30,000 30,019 show-smooth ;
MAIN: smooth-numbers-demo
- Output:
1st through 25th 2-smooth numbers: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 1st through 25th 3-smooth numbers: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 1st through 25th 5-smooth numbers: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 1st through 25th 7-smooth numbers: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 1st through 25th 11-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 1st through 25th 13-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 1st through 25th 17-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 1st through 25th 19-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 1st through 25th 23-smooth numbers: 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 1st through 25th 29-smooth numbers: 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 3,000th through 3,002nd 3-smooth numbers: 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 3,000th through 3,002nd 5-smooth numbers: 278942752080 279936000000 281250000000 3,000th through 3,002nd 7-smooth numbers: 50176000 50331648 50388480 3,000th through 3,002nd 11-smooth numbers: 2112880 2116800 2117016 3,000th through 3,002nd 13-smooth numbers: 390000 390390 390625 3,000th through 3,002nd 17-smooth numbers: 145800 145860 146016 3,000th through 3,002nd 19-smooth numbers: 74256 74358 74360 3,000th through 3,002nd 23-smooth numbers: 46552 46575 46585 3,000th through 3,002nd 29-smooth numbers: 33516 33524 33534 30,000th through 30,019th 503-smooth numbers: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 30,000th through 30,019th 509-smooth numbers: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 30,000th through 30,019th 521-smooth numbers: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
Go
package main
import (
"fmt"
"log"
"math/big"
)
var (
primes []*big.Int
smallPrimes []int
)
// cache all primes up to 521
func init() {
two := big.NewInt(2)
three := big.NewInt(3)
p521 := big.NewInt(521)
p29 := big.NewInt(29)
primes = append(primes, two)
smallPrimes = append(smallPrimes, 2)
for i := three; i.Cmp(p521) <= 0; i.Add(i, two) {
if i.ProbablyPrime(0) {
primes = append(primes, new(big.Int).Set(i))
if i.Cmp(p29) <= 0 {
smallPrimes = append(smallPrimes, int(i.Int64()))
}
}
}
}
func min(bs []*big.Int) *big.Int {
if len(bs) == 0 {
log.Fatal("slice must have at least one element")
}
res := bs[0]
for _, i := range bs[1:] {
if i.Cmp(res) < 0 {
res = i
}
}
return res
}
func nSmooth(n, size int) []*big.Int {
if n < 2 || n > 521 {
log.Fatal("n must be between 2 and 521")
}
if size < 1 {
log.Fatal("size must be at least 1")
}
bn := big.NewInt(int64(n))
ok := false
for _, prime := range primes {
if bn.Cmp(prime) == 0 {
ok = true
break
}
}
if !ok {
log.Fatal("n must be a prime number")
}
ns := make([]*big.Int, size)
ns[0] = big.NewInt(1)
var next []*big.Int
for i := 0; i < len(primes); i++ {
if primes[i].Cmp(bn) > 0 {
break
}
next = append(next, new(big.Int).Set(primes[i]))
}
indices := make([]int, len(next))
for m := 1; m < size; m++ {
ns[m] = new(big.Int).Set(min(next))
for i := 0; i < len(indices); i++ {
if ns[m].Cmp(next[i]) == 0 {
indices[i]++
next[i].Mul(primes[i], ns[indices[i]])
}
}
}
return ns
}
func main() {
for _, i := range smallPrimes {
fmt.Printf("The first 25 %d-smooth numbers are:\n", i)
fmt.Println(nSmooth(i, 25), "\n")
}
for _, i := range smallPrimes[1:] {
fmt.Printf("The 3,000th to 3,202nd %d-smooth numbers are:\n", i)
fmt.Println(nSmooth(i, 3002)[2999:], "\n")
}
for _, i := range []int{503, 509, 521} {
fmt.Printf("The 30,000th to 30,019th %d-smooth numbers are:\n", i)
fmt.Println(nSmooth(i, 30019)[29999:], "\n")
}
}
- Output:
The first 25 2-smooth numbers are: [1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216] The first 25 3-smooth numbers are: [1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192] The first 25 5-smooth numbers are: [1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54] The first 25 7-smooth numbers are: [1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36] The first 25 11-smooth numbers are: [1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32] The first 25 13-smooth numbers are: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28] The first 25 17-smooth numbers are: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27] The first 25 19-smooth numbers are: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26] The first 25 23-smooth numbers are: [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] The first 25 29-smooth numbers are: [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] The 3,000th to 3,202nd 3-smooth numbers are: [91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928] The 3,000th to 3,202nd 5-smooth numbers are: [278942752080 279936000000 281250000000] The 3,000th to 3,202nd 7-smooth numbers are: [50176000 50331648 50388480] The 3,000th to 3,202nd 11-smooth numbers are: [2112880 2116800 2117016] The 3,000th to 3,202nd 13-smooth numbers are: [390000 390390 390625] The 3,000th to 3,202nd 17-smooth numbers are: [145800 145860 146016] The 3,000th to 3,202nd 19-smooth numbers are: [74256 74358 74360] The 3,000th to 3,202nd 23-smooth numbers are: [46552 46575 46585] The 3,000th to 3,202nd 29-smooth numbers are: [33516 33524 33534] The 30,000th to 30,019th 503-smooth numbers are: [62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964] The 30,000th to 30,019th 509-smooth numbers are: [62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646] The 30,000th to 30,019th 521-smooth numbers are: [62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336]
Haskell
The solution is based on the hamming numbers solution Hamming_numbers#Avoiding_generation_of_duplicates.
Uses Library Data.Number.Primes: http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html
import Data.Numbers.Primes (primes)
import Text.Printf (printf)
merge :: Ord a => [a] -> [a] -> [a]
merge [] b = b
merge a@(x:xs) b@(y:ys) | x < y = x : merge xs b
| otherwise = y : merge a ys
nSmooth :: Integer -> [Integer]
nSmooth p = 1 : foldr u [] factors
where
factors = takeWhile (<=p) primes
u n s = r
where r = merge s (map (n*) (1:r))
main :: IO ()
main = do
mapM_ (printf "First 25 %d-smooth:\n%s\n\n" <*> showTwentyFive) firstTenPrimes
mapM_
(printf "The 3,000 to 3,202 %d-smooth numbers are:\n%s\n\n" <*> showRange1)
firstTenPrimes
mapM_
(printf "The 30,000 to 30,019 %d-smooth numbers are:\n%s\n\n" <*> showRange2)
[503, 509, 521]
where
firstTenPrimes = take 10 primes
showTwentyFive = show . take 25 . nSmooth
showRange1 = show . ((<$> [2999 .. 3001]) . (!!) . nSmooth)
showRange2 = show . ((<$> [29999 .. 30018]) . (!!) . nSmooth)
- Output:
First 25 2-smooth: [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216] First 25 3-smooth: [1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192] First 25 5-smooth: [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54] First 25 7-smooth: [1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36] First 25 11-smooth: [1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,27,28,30,32] First 25 13-smooth: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28] First 25 17-smooth: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,27] First 25 19-smooth: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26] First 25 23-smooth: [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] First 25 29-smooth: [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] The 3,000 to 3,202 2-smooth numbers are: [615115961080558588465779406638376257320356947868416857883059014580029400307336474387680033919296729791214824627025902454256442090449118411792541241032674165617479675177922508706511660055680333461312364119878440208217239157846837506706545378604345188396648329405331470912246744225863252651856458002673373954311851336740459676968406552868310201176372388451920238941825550161204650991744181901465270241243954881742049126970364342566022204431867377135606296235889321974743344255860525780985216390373727411888404232090348551541930906092174282761370097898341311102755922756040276005155025127900794674822964000566872737110357506841706953771389531879916938050677117592122548335021080360314705790751185624004215223592421049305160290208996103331123664361061044256821841953835180104581326835320565468498501085250337750687361999383002913789650361626737445306125067585944587449539955645756199886936089259509114994688,1230231922161117176931558813276752514640713895736833715766118029160058800614672948775360067838593459582429649254051804908512884180898236823585082482065348331234959350355845017413023320111360666922624728239756880416434478315693675013413090757208690376793296658810662941824493488451726505303712916005346747908623702673480919353936813105736620402352744776903840477883651100322409301983488363802930540482487909763484098253940728685132044408863734754271212592471778643949486688511721051561970432780747454823776808464180697103083861812184348565522740195796682622205511845512080552010310050255801589349645928001133745474220715013683413907542779063759833876101354235184245096670042160720629411581502371248008430447184842098610320580417992206662247328722122088513643683907670360209162653670641130936997002170500675501374723998766005827579300723253474890612250135171889174899079911291512399773872178519018229989376,2460463844322234353863117626553505029281427791473667431532236058320117601229345897550720135677186919164859298508103609817025768361796473647170164964130696662469918700711690034826046640222721333845249456479513760832868956631387350026826181514417380753586593317621325883648986976903453010607425832010693495817247405346961838707873626211473240804705489553807680955767302200644818603966976727605861080964975819526968196507881457370264088817727469508542425184943557287898973377023442103123940865561494909647553616928361394206167723624368697131045480391593365244411023691024161104020620100511603178699291856002267490948441430027366827815085558127519667752202708470368490193340084321441258823163004742496016860894369684197220641160835984413324494657444244177027287367815340720418325307341282261873994004341001351002749447997532011655158601446506949781224500270343778349798159822583024799547744357038036459978752] The 3,000 to 3,202 3-smooth numbers are: [91580367978306252441724649472,92829823186414819915547541504,94096325042746502515294076928] The 3,000 to 3,202 5-smooth numbers are: [278942752080,279936000000,281250000000] The 3,000 to 3,202 7-smooth numbers are: [50176000,50331648,50388480] The 3,000 to 3,202 11-smooth numbers are: [2112880,2116800,2117016] The 3,000 to 3,202 13-smooth numbers are: [390000,390390,390625] The 3,000 to 3,202 17-smooth numbers are: [145800,145860,146016] The 3,000 to 3,202 19-smooth numbers are: [74256,74358,74360] The 3,000 to 3,202 23-smooth numbers are: [46552,46575,46585] The 3,000 to 3,202 29-smooth numbers are: [33516,33524,33534] The 30,000 to 30,019 503-smooth numbers are: [62913,62914,62916,62918,62920,62923,62926,62928,62930,62933,62935,62937,62944,62946,62951,62952,62953,62957,62959,62964] The 30,000 to 30,019 509-smooth numbers are: [62601,62602,62604,62607,62608,62609,62611,62618,62620,62622,62624,62625,62626,62628,62629,62634,62640,62643,62645,62646] The 30,000 to 30,019 521-smooth numbers are: [62287,62288,62291,62292,62300,62304,62307,62308,62310,62315,62320,62321,62322,62325,62328,62329,62330,62331,62335,62336] ./n-smooth 0.03s user 0.01s system 10% cpu 0.383 total
J
This solution involves sorting, duplicate removal, and limits on the number of preserved terms.
nsmooth=: dyad define NB. TALLY nsmooth N
factors=. x: i.@:>:&.:(p:inv) y
smoothies=. , 1x
result=. , i. 0x
while. x > # result do.
mn =. {. smoothies
smoothies =. ({.~ (x <. #)) ~. /:~ (}. smoothies) , mn * factors
result=. result , mn
end.
)
25 (] ; nsmooth)&> p: i. 10
┌──┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│2 │1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216│
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│3 │1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│5 │1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│7 │1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│11│1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│13│1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│17│1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│19│1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│23│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 │
├──┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│29│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 │
└──┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
3002 (,.@:] ; (_3 {. nsmooth)&>) p: }. i. 10
┌──┬─────────────────────────────────────────────────────────────────────────────────────────┐
│ 3│91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928│
│ 5│ 278942752080 279936000000 281250000000│
│ 7│ 50176000 50331648 50388480│
│11│ 2112880 2116800 2117016│
│13│ 390000 390390 390625│
│17│ 145800 145860 146016│
│19│ 74256 74358 74360│
│23│ 46552 46575 46585│
│29│ 33516 33524 33534│
└──┴─────────────────────────────────────────────────────────────────────────────────────────┘
(i.3)&+&.:(p:inv)503
503 509 521
(30000+20-1) (,.@:] ; (_20 {. nsmooth)&>) (i.3)&+&.:(p:inv)503
┌───┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│503│62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964│
│509│62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646│
│521│62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336│
└───┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
Java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class NSmoothNumbers {
public static void main(String[] args) {
System.out.printf("show the first 25 n-smooth numbers for n = 2 through n = 29%n");
int max = 25;
List<BigInteger> primes = new ArrayList<>();
for ( int n = 2 ; n <= 29 ; n++ ) {
if ( isPrime(n) ) {
primes.add(BigInteger.valueOf(n));
System.out.printf("The first %d %d-smooth numbers:%n", max, n);
BigInteger[] humble = nSmooth(max, primes.toArray(new BigInteger[0]));
for ( int i = 0 ; i < max ; i++ ) {
System.out.printf("%s ", humble[i]);
}
System.out.printf("%n%n");
}
}
System.out.printf("show three numbers starting with 3,000 for n-smooth numbers for n = 3 through n = 29%n");
int count = 3;
max = 3000 + count - 1;
primes = new ArrayList<>();
primes.add(BigInteger.valueOf(2));
for ( int n = 3 ; n <= 29 ; n++ ) {
if ( isPrime(n) ) {
primes.add(BigInteger.valueOf(n));
System.out.printf("The %d through %d %d-smooth numbers:%n", max-count+1, max, n);
BigInteger[] nSmooth = nSmooth(max, primes.toArray(new BigInteger[0]));
for ( int i = max-count ; i < max ; i++ ) {
System.out.printf("%s ", nSmooth[i]);
}
System.out.printf("%n%n");
}
}
System.out.printf("Show twenty numbers starting with 30,000 n-smooth numbers for n=503 through n=521%n");
count = 20;
max = 30000 + count - 1;
primes = new ArrayList<>();
for ( int n = 2 ; n <= 521 ; n++ ) {
if ( isPrime(n) ) {
primes.add(BigInteger.valueOf(n));
if ( n >= 503 && n <= 521 ) {
System.out.printf("The %d through %d %d-smooth numbers:%n", max-count+1, max, n);
BigInteger[] nSmooth = nSmooth(max, primes.toArray(new BigInteger[0]));
for ( int i = max-count ; i < max ; i++ ) {
System.out.printf("%s ", nSmooth[i]);
}
System.out.printf("%n%n");
}
}
}
}
private static final boolean isPrime(long test) {
if ( test == 2 ) {
return true;
}
if ( test % 2 == 0 ) return false;
for ( long i = 3 ; i <= Math.sqrt(test) ; i += 2 ) {
if ( test % i == 0 ) {
return false;
}
}
return true;
}
private static BigInteger[] nSmooth(int n, BigInteger[] primes) {
int size = primes.length;
BigInteger[] test = new BigInteger[size];
for ( int i = 0 ; i < size ; i++ ) {
test[i] = primes[i];
}
BigInteger[] results = new BigInteger[n];
results[0] = BigInteger.ONE;
int[] indexes = new int[size];
for ( int i = 0 ; i < size ; i++ ) {
indexes[i] = 0;
}
for ( int index = 1 ; index < n ; index++ ) {
BigInteger min = test[0];
for ( int i = 1 ; i < size ; i++ ) {
min = min.min(test[i]);
}
results[index] = min;
for ( int i = 0 ; i < size ; i++ ) {
if ( results[index].compareTo(test[i]) == 0 ) {
indexes[i] = indexes[i] + 1;
test[i] = primes[i].multiply(results[indexes[i]]);
}
}
}
return results;
}
}
- Output:
show the first 25 n-smooth numbers for n = 2 through n = 29 The first 25 2-smooth numbers: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 The first 25 3-smooth numbers: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 The first 25 5-smooth numbers: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 The first 25 7-smooth numbers: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 The first 25 11-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 The first 25 13-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 The first 25 17-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 The first 25 19-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 The first 25 23-smooth numbers: 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 The first 25 29-smooth numbers: 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 show three numbers starting with 3,000 for n-smooth numbers for n = 3 through n = 29 The 3000 through 3002 3-smooth numbers: 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 The 3000 through 3002 5-smooth numbers: 278942752080 279936000000 281250000000 The 3000 through 3002 7-smooth numbers: 50176000 50331648 50388480 The 3000 through 3002 11-smooth numbers: 2112880 2116800 2117016 The 3000 through 3002 13-smooth numbers: 390000 390390 390625 The 3000 through 3002 17-smooth numbers: 145800 145860 146016 The 3000 through 3002 19-smooth numbers: 74256 74358 74360 The 3000 through 3002 23-smooth numbers: 46552 46575 46585 The 3000 through 3002 29-smooth numbers: 33516 33524 33534 Show twenty numbers starting with 30,000 n-smooth numbers for n=503 through n=521 The 30000 through 30019 503-smooth numbers: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 The 30000 through 30019 509-smooth numbers: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 The 30000 through 30019 521-smooth numbers: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
JavaScript
function isPrime(n){
var x = Math.floor(Math.sqrt(n)), i = 2
while ((i <= x) && (n % i != 0)) i++
return (x < i)
}
function smooth(n, s, k){
var p = []
for (let i = 2; i <= n; i++){
if (isPrime(i)){
p.push([BigInt(i), [1n], 0])
}
}
var res = []
for (let i = 0; i < s + k; i++){
var m = p[0][1][p[0][2]]
for (let j = 1; j < p.length; j++){
if (p[j][1][p[j][2]] < m) m = p[j][1][p[j][2]]
}
for (let j = 0; j < p.length; j++){
p[j][1].push(p[j][0]*m)
if (p[j][1][p[j][2]] == m) p[j][2]++
}
res.push(m)
}
return res.slice(s-1, s-1+k);
}
// main
var sOut = ""
for (let x of [[2, 29, 1, 25], [3, 29, 3000, 3], [503, 521, 30000, 20]]){
for (let n = x[0]; n <= x[1]; n++){
if (isPrime(n)){
sOut += x[2] + " to " + (x[2] - 1 + x[3]) + " " + n + "-smooth numbers: " + smooth(n, x[2], x[3]) + "\n"
}
}
}
console.log(sOut)
- Output:
1 to 25 2-smooth numbers: 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216 1 to 25 3-smooth numbers: 1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192 1 to 25 5-smooth numbers: 1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54 1 to 25 7-smooth numbers: 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36 1 to 25 11-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,27,28,30,32 1 to 25 13-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28 1 to 25 17-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,27 1 to 25 19-smooth numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26 1 to 25 23-smooth numbers: 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 1 to 25 29-smooth numbers: 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 3000 to 3002 3-smooth numbers: 91580367978306252441724649472,92829823186414819915547541504,94096325042746502515294076928 3000 to 3002 5-smooth numbers: 278942752080,279936000000,281250000000 3000 to 3002 7-smooth numbers: 50176000,50331648,50388480 3000 to 3002 11-smooth numbers: 2112880,2116800,2117016 3000 to 3002 13-smooth numbers: 390000,390390,390625 3000 to 3002 17-smooth numbers: 145800,145860,146016 3000 to 3002 19-smooth numbers: 74256,74358,74360 3000 to 3002 23-smooth numbers: 46552,46575,46585 3000 to 3002 29-smooth numbers: 33516,33524,33534 30000 to 30019 503-smooth numbers: 62913,62914,62916,62918,62920,62923,62926,62928,62930,62933,62935,62937,62944,62946,62951,62952,62953,62957,62959,62964 30000 to 30019 509-smooth numbers: 62601,62602,62604,62607,62608,62609,62611,62618,62620,62622,62624,62625,62626,62628,62629,62634,62640,62643,62645,62646 30000 to 30019 521-smooth numbers: 62287,62288,62291,62292,62300,62304,62307,62308,62310,62315,62320,62321,62322,62325,62328,62329,62330,62331,62335,62336
Julia
using Primes
function nsmooth(N, needed)
nexts, smooths = [BigInt(i) for i in 2:N if isprime(i)], [BigInt(1)]
prim, count = deepcopy(nexts), 1
indices = ones(Int, length(nexts))
while count < needed
x = minimum(nexts)
push!(smooths, x)
count += 1
for j in 1:length(nexts)
(nexts[j] <= x) && (nexts[j] = prim[j] * smooths[(indices[j] += 1)])
end
end
return (smooths[end] > typemax(Int)) ? smooths : Int.(smooths)
end
function testnsmoothfilters()
for i in filter(isprime, 1:29)
println("The first 25 n-smooth numbers for n = $i are: ", nsmooth(i, 25))
end
for i in filter(isprime, 3:29)
println("The 3000th through 3002nd ($i)-smooth numbers are: ", nsmooth(i, 3002)[3000:3002])
end
for i in filter(isprime, 503:521)
println("The 30000th through 30019th ($i)-smooth numbers >= 30000 are: ", nsmooth(i, 30019)[30000:30019])
end
end
testnsmoothfilters()
- Output:
The first 25 n-smooth numbers for n = 2 are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 25 n-smooth numbers for n = 3 are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 25 n-smooth numbers for n = 5 are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 25 n-smooth numbers for n = 7 are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 25 n-smooth numbers for n = 11 are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 25 n-smooth numbers for n = 13 are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 25 n-smooth numbers for n = 17 are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 25 n-smooth numbers for n = 19 are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 25 n-smooth numbers for n = 23 are: [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] The first 25 n-smooth numbers for n = 29 are: [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] The 3000th through 3002nd (3)-smooth numbers are: BigInt[91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3000th through 3002nd (5)-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3000th through 3002nd (7)-smooth numbers are: [50176000, 50331648, 50388480] The 3000th through 3002nd (11)-smooth numbers are: [2112880, 2116800, 2117016] The 3000th through 3002nd (13)-smooth numbers are: [390000, 390390, 390625] The 3000th through 3002nd (17)-smooth numbers are: [145800, 145860, 146016] The 3000th through 3002nd (19)-smooth numbers are: [74256, 74358, 74360] The 3000th through 3002nd (23)-smooth numbers are: [46552, 46575, 46585] The 3000th through 3002nd (29)-smooth numbers are: [33516, 33524, 33534] The 30000th through 30019th (503)-smooth numbers >= 30000 are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30000th through 30019th (509)-smooth numbers >= 30000 are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30000th through 30019th (521)-smooth numbers >= 30000 are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Kotlin
import java.math.BigInteger
var primes = mutableListOf<BigInteger>()
var smallPrimes = mutableListOf<Int>()
// cache all primes up to 521
fun init() {
val two = BigInteger.valueOf(2)
val three = BigInteger.valueOf(3)
val p521 = BigInteger.valueOf(521)
val p29 = BigInteger.valueOf(29)
primes.add(two)
smallPrimes.add(2)
var i = three
while (i <= p521) {
if (i.isProbablePrime(1)) {
primes.add(i)
if (i <= p29) {
smallPrimes.add(i.toInt())
}
}
i += two
}
}
fun min(bs: List<BigInteger>): BigInteger {
require(bs.isNotEmpty()) { "slice must have at lease one element" }
val it = bs.iterator()
var res = it.next()
while (it.hasNext()) {
val t = it.next()
if (t < res) {
res = t
}
}
return res
}
fun nSmooth(n: Int, size: Int): List<BigInteger> {
require(n in 2..521) { "n must be between 2 and 521" }
require(size >= 1) { "size must be at least 1" }
val bn = BigInteger.valueOf(n.toLong())
var ok = false
for (prime in primes) {
if (bn == prime) {
ok = true
break
}
}
require(ok) { "n must be a prime number" }
val ns = Array<BigInteger>(size) { BigInteger.ZERO }
ns[0] = BigInteger.ONE
val next = mutableListOf<BigInteger>()
for (i in 0 until primes.size) {
if (primes[i] > bn) {
break
}
next.add(primes[i])
}
val indices = Array(next.size) { 0 }
for (m in 1 until size) {
ns[m] = min(next)
for (i in indices.indices) {
if (ns[m] == next[i]) {
indices[i]++
next[i] = primes[i] * ns[indices[i]]
}
}
}
return ns.toList()
}
fun main() {
init()
for (i in smallPrimes) {
println("The first 25 $i-smooth numbers are:")
println(nSmooth(i, 25))
println()
}
for (i in smallPrimes.drop(1)) {
println("The 3,000th to 3,202 $i-smooth numbers are:")
println(nSmooth(i, 3_002).drop(2_999))
println()
}
for (i in listOf(503, 509, 521)) {
println("The 30,000th to 30,019 $i-smooth numbers are:")
println(nSmooth(i, 30_019).drop(29_999))
println()
}
}
- Output:
The first 25 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 25 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 25 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 25 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 25 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 25 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 25 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 25 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 25 23-smooth numbers are: [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] The first 25 29-smooth numbers are: [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] The 3,000th to 3,202 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3,000th to 3,202 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3,000th to 3,202 7-smooth numbers are: [50176000, 50331648, 50388480] The 3,000th to 3,202 11-smooth numbers are: [2112880, 2116800, 2117016] The 3,000th to 3,202 13-smooth numbers are: [390000, 390390, 390625] The 3,000th to 3,202 17-smooth numbers are: [145800, 145860, 146016] The 3,000th to 3,202 19-smooth numbers are: [74256, 74358, 74360] The 3,000th to 3,202 23-smooth numbers are: [46552, 46575, 46585] The 3,000th to 3,202 29-smooth numbers are: [33516, 33524, 33534] The 30,000th to 30,019 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000th to 30,019 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000th to 30,019 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Mathematica / Wolfram Language
ClearAll[GenerateSmoothNumbers]
GenerateSmoothNumbers[max_?Positive] := GenerateSmoothNumbers[max, 7]
GenerateSmoothNumbers[max_?Positive, maxprime_?Positive] :=
Module[{primes, len, vars, body, endspecs, its, data},
primes = Prime[Range[PrimePi[maxprime]]];
len = Length[primes];
If[max < Min[primes],
{}
,
vars = Table[Unique[], len];
body = Times @@ (primes^vars);
endspecs = Prepend[Most[primes^vars], 1];
endspecs = FoldList[Times, endspecs];
its = Transpose[{vars, ConstantArray[0, len], MapThread[N@Log[#1, max/#2] &, {primes, endspecs}]}];
With[{b = body, is = its},
data = Table[b, Evaluate[Sequence @@ is]];
];
data = Sort[Flatten[data]];
data
]
]
Take[GenerateSmoothNumbers[10^8, 2], 25]
Take[GenerateSmoothNumbers[200, 3], 25]
Take[GenerateSmoothNumbers[200, 5], 25]
Take[GenerateSmoothNumbers[200, 7], 25]
Take[GenerateSmoothNumbers[200, 11], 25]
Take[GenerateSmoothNumbers[200, 13], 25]
Take[GenerateSmoothNumbers[200, 17], 25]
Take[GenerateSmoothNumbers[200, 19], 25]
Take[GenerateSmoothNumbers[200, 23], 25]
Take[GenerateSmoothNumbers[200, 29], 25]
Take[GenerateSmoothNumbers[10^40, 3], {3000, 3002}]
Take[GenerateSmoothNumbers[10^15, 5], {3000, 3002}]
Take[GenerateSmoothNumbers[10^10, 7], {3000, 3002}]
Take[GenerateSmoothNumbers[10^7, 11], {3000, 3002}]
Take[GenerateSmoothNumbers[10^7, 13], {3000, 3002}]
Take[GenerateSmoothNumbers[10^6, 17], {3000, 3002}]
Take[GenerateSmoothNumbers[10^5, 19], {3000, 3002}]
Take[GenerateSmoothNumbers[10^5, 23], {3000, 3002}]
Take[GenerateSmoothNumbers[10^5, 29], {3000, 3002}]
s = Select[Range[10^5], FactorInteger /* Last /* First /* LessEqualThan[503]];
s[[30000 ;; 30019]]
s = Select[Range[10^5], FactorInteger /* Last /* First /* LessEqualThan[509]];
s[[30000 ;; 30019]]
s = Select[Range[10^5], FactorInteger /* Last /* First /* LessEqualThan[521]];
s[[30000 ;; 30019]]
- Output:
{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216}
{1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192}
{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54}
{1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,30,32,35,36}
{1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,27,28,30,32}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,27}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26}
{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}
{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}
{91580367978306252441724649472,92829823186414819915547541504,94096325042746502515294076928}
{278942752080,279936000000,281250000000}
{50176000,50331648,50388480}
{2112880,2116800,2117016}
{390000,390390,390625}
{145800,145860,146016}
{74256,74358,74360}
{46552,46575,46585}
{33516,33524,33534}
{62913,62914,62916,62918,62920,62923,62926,62928,62930,62933,62935,62937,62944,62946,62951,62952,62953,62957,62959,62964}
{62601,62602,62604,62607,62608,62609,62611,62618,62620,62622,62624,62625,62626,62628,62629,62634,62640,62643,62645,62646}
{62287,62288,62291,62292,62300,62304,62307,62308,62310,62315,62320,62321,62322,62325,62328,62329,62330,62331,62335,62336}
Nim
Translation of Kotlin except for the search of primes where we have chosen to use a sieve of Eratosthenes.
import sequtils, strutils
import bignum
const N = 521
func initPrimes(): tuple[primes: seq[Int]; smallPrimes: seq[int]] =
var sieve: array[2..N, bool]
for n in 2..N:
if not sieve[n]:
for k in countup(n * n, N, n): sieve[k] = true
for n, isComposite in sieve:
if not isComposite:
result.primes.add newInt(n)
if n <= 29: result.smallPrimes.add n
# Cache all primes up to N.
let (Primes, SmallPrimes) = initPrimes()
proc nSmooth(n, size: Positive): seq[Int] =
assert n in 2..N, "'n' must be between 2 and " & $N
let bn = newInt(n)
assert bn in Primes, "'n' must be a prime number"
result.setLen(size)
result[0] = newInt(1)
var next: seq[Int]
for prime in Primes:
if prime > bn: break
next.add prime
var indices = newSeq[int](next.len)
for m in 1..<size:
result[m] = next[next.minIndex()]
for i in 0..indices.high:
if result[m] == next[i]:
inc indices[i]
next[i] = Primes[i] * result[indices[i]]
when isMainModule:
for n in SmallPrimes:
echo "The first ", n, "-smooth numbers are:"
echo nSmooth(n, 25).join(" ")
echo ""
for n in SmallPrimes[1..^1]:
echo "The 3000th to 3202th ", n, "-smooth numbers are:"
echo nSmooth(n, 3002)[2999..^1].join(" ")
echo ""
for n in [503, 509, 521]:
echo "The 30000th to 30019th ", n, "-smooth numbers are:"
echo nSmooth(n, 30_019)[29_999..^1].join(" ")
echo ""
- Output:
The first 2-smooth numbers are: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 The first 3-smooth numbers are: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 The first 5-smooth numbers are: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 The first 7-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 The first 11-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 The first 13-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 The first 17-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 The first 19-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 The first 23-smooth numbers are: 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 The first 29-smooth numbers are: 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 The 3000th to 3202th 3-smooth numbers are: 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 The 3000th to 3202th 5-smooth numbers are: 278942752080 279936000000 281250000000 The 3000th to 3202th 7-smooth numbers are: 50176000 50331648 50388480 The 3000th to 3202th 11-smooth numbers are: 2112880 2116800 2117016 The 3000th to 3202th 13-smooth numbers are: 390000 390390 390625 The 3000th to 3202th 17-smooth numbers are: 145800 145860 146016 The 3000th to 3202th 19-smooth numbers are: 74256 74358 74360 The 3000th to 3202th 23-smooth numbers are: 46552 46575 46585 The 3000th to 3202th 29-smooth numbers are: 33516 33524 33534 The 30000th to 30019th 503-smooth numbers are: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 The 30000th to 30019th 509-smooth numbers are: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 The 30000th to 30019th 521-smooth numbers are: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
PARI/GP
upto(n, V0= primes(3) )= { /* default 3: [2,3,5] */
my( N= #V0, r= Vec([1],n), v= V0, ix= vector(N,i,1), t );
for(m= 2, n
, r[m]= t= vecmin(v);
for(i= 1, N
, if( v[i] == t, v[i]= V0[i] * r[ix[i]++] );
);
);r
}
S7(n)= upto(n, primes(4))[n]; /* 7-smooth */
upto(20) /* 5-smooth */
S7(1691)
S7(10^6)- Output:
%1 = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36] %2 = 3317760 %3 = 4157409948433216829957008507500000000
Pascal
program nSmoothNumbers(output);
const
primeCount = 538;
{$ifDef __GPC__} {$setLimit=3889} {$endIf}
cardinalMax = 3888;
type
cardinal = 0..cardinalMax;
cardinals = set of cardinal;
cardinalPositive = 1..cardinalMax;
natural = 1..maxInt;
primeIndex = 1..primeCount;
list = array[primeIndex] of cardinal;
var
prime: list;
{
\brief performs prime factorization
\param n the number to factorize
\return list of exponents for a unique integer factorization using primes
This function requires the global `prime` variable to be initialized.
}
function primeFactorization(n: natural): list;
var
i: primeIndex;
{
Instead of writing `[1: 0; 2: 0; 3: 0; …]`, Extended Pascal permits us
to use an “array completer” for all unspecified values.
}
result: list value [otherwise 0];
begin
for i := 1 to primeCount do
begin
while n mod prime[i] = 0 do
begin
n := n div prime[i];
result[i] := result[i] + 1
end
end;
{ Nullify result if the utilized `prime` list was insufficient. }
if n <> 1 then
begin
{ `array` literals need an explicit data type specification. }
result := list[otherwise 0]
end;
{
In a Pascal function definition there must be _one_ assignment to the
(implicitly) declared variable bearing the same name as of the function.
This will be returned function result.
}
primeFactorization := result
end;
{
\brief returns whether a number is an n-smooth number
\param smoothness the maximum permissible prime factor
\param x the number to check
\return whether \param x is smoothness-smooth
}
function isSmooth(
protected smoothness: cardinalPositive;
protected x: natural
): Boolean;
{
Return set of non-one factors (i.e. non-zero exponent).
Nesting this function permits most compilers to allocate memory
for variables only if the function is actually needed.
}
function factorizationBases: cardinals;
var
exponent: list;
i: primeIndex;
result: cardinals value [];
begin
exponent := primeFactorization(x);
for i := 1 to primeCount do
begin
if exponent[i] > 0 then
begin
result := result + [prime[i]]
end
end;
factorizationBases := result
end;
begin
case smoothness of
1:
begin
{
The value `1` actually does not have a prime factorization, yet as per
task specification “1 (unity) is always included in n‑smooth numbers.”
}
isSmooth := x = 1
end;
{ 2‑smooth numbers is an alias for powers of 2 (OEIS sequence A000079) }
2:
begin
isSmooth := 2 pow round(ln(x) / ln(2)) = x
end
{ The `otherwise` catch-all-clause is an Extended Pascal extension. }
otherwise
begin
isSmooth := card(factorizationBases - [0..smoothness]) = 0
{
`card` (“cardinality”) is an Extended Pascal extension.
Testing `card(M) = 0` is equivalent to `M = []` (empty set).
}
end
end
end;
{ === ancillary routines =============================================== }
{ This is just your regular Eratosthenes prime sieve. }
procedure sieve(var primes: cardinals);
var
n: natural;
i: integer;
multiples: cardinals;
begin
{ `1` is by definition not a prime number }
primes := primes - [1];
{ find the next non-crossed number }
for n := 2 to cardinalMax do
begin
if n in primes then
begin
multiples := [];
{ We do _not_ want to remove 1 * n. }
i := 2 * n;
while i in [n..cardinalMax] do
begin
multiples := multiples + [i];
i := i + n
end;
primes := primes - multiples
end
end
end;
{ This procedure transforms a `set` to an `array`. }
procedure populatePrime;
var
primes: cardinals value [1..cardinalMax];
n: natural value 1;
i: primeIndex value 1;
begin
sieve(primes);
for i := 1 to primeCount do
begin
repeat
begin
n := n + 1
end
until n in primes;
prime[i] := n
end
end;
{ ### MAIN ############################################################# }
var
i: primeIndex value primeCount;
candidate: natural;
count: cardinal;
begin
populatePrime;
{ Show the first 25 n-smooth numbers […] }
{ […] only prime [n] are to be used. }
while prime[i] > 29 do
begin
i := i - 1
end;
{
In Pascal, `for` loop limits are evaluated _once_,
so this is perfectly legal:
}
for i := 1 to i do
begin
write(prime[i]:4, '-smooth: 1');
count := 1; { `1` already listed. }
candidate := 2;
while count < 25 do
begin
if isSmooth(prime[i], candidate) then
begin
write(', ', candidate:1);
count := count + 1
end;
candidate := candidate + 1
end;
writeLn
end;
{
Note, in Pascal, the `for`‑loop iteration variable is not modified.
At this point in the code, `i` (still) has the value after the `while`-loop.
[This statement is not true, if a `goto` prematurely exited the `for`‑loop.]
}
writeLn;
{ […] show three numbers starting with 3,000 […] }
for i := 2 to i do
begin
write(prime[i]:4, '-smooth:');
count := 0;
candidate := 3000;
while count < 3 do
begin
if isSmooth(prime[i], candidate) then
begin
write(' ', candidate:1);
count := count + 1
end;
candidate := candidate + 1
end;
writeLn
end;
end.
- Output:
2-smooth: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216 3-smooth: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192 5-smooth: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54 7-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36 11-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32 13-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28 17-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27 19-smooth: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26 23-smooth: 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 29-smooth: 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 3-smooth: 3072 3456 3888 5-smooth: 3000 3072 3125 7-smooth: 3000 3024 3072 11-smooth: 3000 3024 3025 13-smooth: 3000 3003 3024 17-smooth: 3000 3003 3024 19-smooth: 3000 3003 3024 23-smooth: 3000 3003 3024 29-smooth: 3000 3003 3016
Perl
use strict;
use warnings;
use feature 'say';
use ntheory qw<primes>;
use List::Util qw<min>;
#use bigint # works, but slow
use Math::GMPz; # this module gives roughly 16x speed-up
sub smooth_numbers {
# my(@m) = @_; # use with 'bigint'
my @m = map { Math::GMPz->new($_) } @_; # comment out to NOT use Math::GMPz
my @s;
push @s, [1] for 0..$#m;
return sub {
my $n = $s[0][0];
$n = min $n, $s[$_][0] for 1..$#m;
for (0..$#m) {
shift @{$s[$_]} if $s[$_][0] == $n;
push @{$s[$_]}, $n * $m[$_]
}
return $n
}
}
sub abbrev {
my($n) = @_;
return $n if length($n) <= 50;
substr($n,0,10) . "...(@{[length($n) - 2*10]} digits omitted)..." . substr($n, -10, 10)
}
my @primes = @{primes(10_000)};
my $start = 3000; my $cnt = 3;
for my $n_smooth (0..9) {
say "\nFirst 25, and ${start}th through @{[$start+2]}nd $primes[$n_smooth]-smooth numbers:";
my $s = smooth_numbers(@primes[0..$n_smooth]);
my @S25;
push @S25, $s->() for 1..25;
say join ' ', @S25;
my @Sm; my $c = 25;
do {
my $sn = $s->();
push @Sm, abbrev($sn) if ++$c >= $start;
} until @Sm == $cnt;
say join ' ', @Sm;
}
$start = 30000; $cnt = 20;
for my $n_smooth (95..97) { # (503, 509, 521) {
say "\n${start}th through @{[$start+$cnt-1]}th $primes[$n_smooth]-smooth numbers:";
my $s = smooth_numbers(@primes[0..$n_smooth]);
my(@Sm,$c);
do {
my $sn = $s->();
push @Sm, $sn if ++$c >= $start;
} until @Sm == $cnt;
say join ' ', @Sm;
}
- Output:
First 25, and 3000th through 3002nd 2-smooth numbers: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 6151159610...(883 digits omitted)...9114994688 1230231922...(884 digits omitted)...8229989376 2460463844...(884 digits omitted)...6459978752 First 25, and 3000th through 3002nd 3-smooth numbers: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 First 25, and 3000th through 3002nd 5-smooth numbers: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 278942752080 279936000000 281250000000 First 25, and 3000th through 3002nd 7-smooth numbers: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 50176000 50331648 50388480 First 25, and 3000th through 3002nd 11-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 2112880 2116800 2117016 First 25, and 3000th through 3002nd 13-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 390000 390390 390625 First 25, and 3000th through 3002nd 17-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 145800 145860 146016 First 25, and 3000th through 3002nd 19-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 74256 74358 74360 First 25, and 3000th through 3002nd 23-smooth numbers: 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 46552 46575 46585 First 25, and 3000th through 3002nd 29-smooth numbers: 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 33516 33524 33534 30000th through 30019th 503-smooth numbers: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 30000th through 30019th 509-smooth numbers: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 30000th through 30019th 521-smooth numbers: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
Phix
with javascript_semantics include mpfr.e function nsmooth(integer n, integer needed) -- note that n is a prime index, ie 1,2,3,4... for 2,3,5,7... sequence smooth = {mpz_init(1)}, nexts = get_primes(-n), indices = repeat(1,n) for i=1 to n do nexts[i] = mpz_init(nexts[i]) end for for i=2 to needed do mpz x = mpz_init_set(mpz_min(nexts)) smooth = append(smooth,x) for j=1 to n do if mpz_cmp(nexts[j],x)<=0 then indices[j] += 1 mpz_mul_si(nexts[j],smooth[indices[j]],get_prime(j)) end if end for end for return smooth end function function flat_str(sequence s) for i=1 to length(s) do s[i] = shorten(mpz_get_str(s[i]),ml:=10) end for return join(s," ") end function for n=1 to 10 do printf(1,"%d-smooth[1..25]: %s\n",{get_prime(n),flat_str(nsmooth(n, 25))}) end for for n=1 to 10 do printf(1,"%d-smooth[3000..3002]: %s\n",{get_prime(n),flat_str(nsmooth(n, 3002)[3000..3002])}) end for for n=96 to 98 do -- primes 503, 509, and 521 printf(1,"%d-smooth[30000..30019]: %s\n",{get_prime(n),flat_str(nsmooth(n, 30019)[30000..30019])}) end for
- Output:
2-smooth[1..25]: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 3-smooth[1..25]: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 5-smooth[1..25]: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 7-smooth[1..25]: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 11-smooth[1..25]: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 13-smooth[1..25]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 17-smooth[1..25]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 19-smooth[1..25]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 23-smooth[1..25]: 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 29-smooth[1..25]: 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 2-smooth[3000..3002]: 615115961...114994688 (903 digits) 123023192...229989376 (904 digits) 246046384...459978752 (904 digits) 3-smooth[3000..3002]: 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 5-smooth[3000..3002]: 278942752080 279936000000 281250000000 7-smooth[3000..3002]: 50176000 50331648 50388480 11-smooth[3000..3002]: 2112880 2116800 2117016 13-smooth[3000..3002]: 390000 390390 390625 17-smooth[3000..3002]: 145800 145860 146016 19-smooth[3000..3002]: 74256 74358 74360 23-smooth[3000..3002]: 46552 46575 46585 29-smooth[3000..3002]: 33516 33524 33534 503-smooth[30000..30019]: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 509-smooth[30000..30019]: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 521-smooth[30000..30019]: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
Python
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
def isPrime(n):
if n < 2:
return False
for i in primes:
if n == i:
return True
if n % i == 0:
return False
if i * i > n:
return True
print "Oops,", n, " is too large"
def init():
s = 24
while s < 600:
if isPrime(s - 1) and s - 1 > primes[-1]:
primes.append(s - 1)
if isPrime(s + 1) and s + 1 > primes[-1]:
primes.append(s + 1)
s += 6
def nsmooth(n, size):
if n < 2 or n > 521:
raise Exception("n")
if size < 1:
raise Exception("n")
bn = n
ok = False
for prime in primes:
if bn == prime:
ok = True
break
if not ok:
raise Exception("must be a prime number: n")
ns = [0] * size
ns[0] = 1
next = []
for prime in primes:
if prime > bn:
break
next.append(prime)
indicies = [0] * len(next)
for m in xrange(1, size):
ns[m] = min(next)
for i in xrange(0, len(indicies)):
if ns[m] == next[i]:
indicies[i] += 1
next[i] = primes[i] * ns[indicies[i]]
return ns
def main():
init()
for p in primes:
if p >= 30:
break
print "The first", p, "-smooth numbers are:"
print nsmooth(p, 25)
print
for p in primes[1:]:
if p >= 30:
break
print "The 3000 to 3202", p, "-smooth numbers are:"
print nsmooth(p, 3002)[2999:]
print
for p in [503, 509, 521]:
print "The 30000 to 3019", p, "-smooth numbers are:"
print nsmooth(p, 30019)[29999:]
print
main()
- Output:
The first 2 -smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 3 -smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 5 -smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 7 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 11 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 13 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 17 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 19 -smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 23 -smooth numbers are: [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] The first 29 -smooth numbers are: [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] The 3000 to 3202 3 -smooth numbers are: [91580367978306252441724649472L, 92829823186414819915547541504L, 94096325042746502515294076928L] The 3000 to 3202 5 -smooth numbers are: [278942752080L, 279936000000L, 281250000000L] The 3000 to 3202 7 -smooth numbers are: [50176000, 50331648, 50388480] The 3000 to 3202 11 -smooth numbers are: [2112880, 2116800, 2117016] The 3000 to 3202 13 -smooth numbers are: [390000, 390390, 390625] The 3000 to 3202 17 -smooth numbers are: [145800, 145860, 146016] The 3000 to 3202 19 -smooth numbers are: [74256, 74358, 74360] The 3000 to 3202 23 -smooth numbers are: [46552, 46575, 46585] The 3000 to 3202 29 -smooth numbers are: [33516, 33524, 33534] The 30000 to 3019 503 -smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30000 to 3019 509 -smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30000 to 3019 521 -smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Quackery
[ behead 0 swap rot
witheach
[ 2dup < iff
drop done
nip nip
i^ 1+ swap ] ] is smallest ( [ --> n n )
[ stack ] is end.test ( --> s )
[ ]'[ end.test put
dup temp put
' [ 1 ]
0 rot size of
[ over end.test share do if done
[] unrot
dup dip
[ witheach
[ dip dup peek
temp share i^ peek *
rot swap join swap ] ]
rot smallest
dip
[ 2dup peek 1+ unrot poke ]
rot swap over
-1 peek over = iff
drop else join
swap again ]
drop
end.test release
temp release ] is smoothwith ( [ --> [ )
[ ' [ 2 3 5 7 11 13 17 19 23 29 ]
swap split drop ] is primes ( n --> [ )
10 times
[ i^ 1+ primes
smoothwith [ size 25 = ]
echo cr ]
cr
9 times
[ i^ 2 + primes
smoothwith [ size 3002 = ]
-3 split nip echo cr ]- Output:
[ 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 ] [ 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 ] [ 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 ] [ 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 ] [ 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 ] [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 ] [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 ] [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 ] [ 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 ] [ 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 ] [ 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 ] [ 278942752080 279936000000 281250000000 ] [ 50176000 50331648 50388480 ] [ 2112880 2116800 2117016 ] [ 390000 390390 390625 ] [ 145800 145860 146016 ] [ 74256 74358 74360 ] [ 46552 46575 46585 ] [ 33516 33524 33534 ]
Raku
(formerly Perl 6)
sub smooth-numbers (*@list) {
cache my \Smooth := gather {
my %i = (flat @list) Z=> (Smooth.iterator for ^@list);
my %n = (flat @list) Z=> 1 xx *;
loop {
take my $n := %n{*}.min;
for @list -> \k {
%n{k} = %i{k}.pull-one * k if %n{k} == $n;
}
}
}
}
sub abbrev ($n) {
$n.chars > 50 ??
$n.substr(0,10) ~ "...({$n.chars - 20} digits omitted)..." ~ $n.substr(* - 10) !!
$n
}
my @primes = (2..*).grep: *.is-prime;
my $start = 3000;
for ^@primes.first( * > 29, :k ) -> $p {
put join "\n", "\nFirst 25, and {$start}th through {$start+2}nd {@primes[$p]}-smooth numbers:",
$(smooth-numbers(|@primes[0..$p])[^25]),
$(smooth-numbers(|@primes[0..$p])[$start - 1 .. $start + 1]».&abbrev);
}
$start = 30000;
for 503, 509, 521 -> $p {
my $i = @primes.first( * == $p, :k );
put "\n{$start}th through {$start+19}th {@primes[$i]}-smooth numbers:\n" ~
smooth-numbers(|@primes[0..$i])[$start - 1 .. $start + 18];
}
- Output:
First 25, and 3000th through 3002nd 2-smooth numbers: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 6151159610...(883 digits omitted)...9114994688 1230231922...(884 digits omitted)...8229989376 2460463844...(884 digits omitted)...6459978752 First 25, and 3000th through 3002nd 3-smooth numbers: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 First 25, and 3000th through 3002nd 5-smooth numbers: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 278942752080 279936000000 281250000000 First 25, and 3000th through 3002nd 7-smooth numbers: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 50176000 50331648 50388480 First 25, and 3000th through 3002nd 11-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 2112880 2116800 2117016 First 25, and 3000th through 3002nd 13-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 390000 390390 390625 First 25, and 3000th through 3002nd 17-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 145800 145860 146016 First 25, and 3000th through 3002nd 19-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 74256 74358 74360 First 25, and 3000th through 3002nd 23-smooth numbers: 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 46552 46575 46585 First 25, and 3000th through 3002nd 29-smooth numbers: 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 33516 33524 33534 30000th through 30019th 503-smooth numbers: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 30000th through 30019th 509-smooth numbers: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 30000th through 30019th 521-smooth numbers: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
REXX
/*REXX pgm computes&displays X n-smooth numbers; both X and N can be specified as ranges*/
numeric digits 200 /*be able to handle some big numbers. */
parse arg LOx HIx LOn HIn . /*obtain optional arguments from the CL*/
if LOx=='' | LOx=="," then LOx= 1 /*Not specified? Then use the default.*/
if HIx=='' | HIx=="," then HIx= LOx + 24 /* " " " " " " */
if LOn=='' | LOn=="," then LOn= 2 /* " " " " " " */
if HIn=='' | HIn=="," then HIn= LOn + 27 /* " " " " " " */
call genP HIn /*generate enough primes to satisfy HIn*/
@aList= ' a list of the '; @thru= ' through ' /*literals used with a SAY.*/
do j=LOn to HIn; if !.j==0 then iterate /*if not prime, then skip this number. */
call smooth HIx,j; $= /*invoke SMOOTH; initialize $ (list). */
do k=LOx to HIx; $= $ #.k /*append a smooth number to " " " */
end /*k*/
say center(@aList th(LOx) @thru th(HIx) ' numbers for' j"-smooth ", 130, "═")
say strip($); say
end /*j*/ /* [↑] the $ list has a leading blank.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: procedure expose @. !. #; parse arg x /*#≡num of primes; @. ≡array of primes.*/
@.=; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19; @.9=23; #=9
!.=0; !.2=1; !.3=2; !.5=3; !.7=4; !.11=5; !.13=6; !.17=7; !.19=8; !.23=9
do k=@.#+6 by 2 until #>=x ; if k//3==0 then iterate
parse var k '' -1 _; if _==5 then iterate
do d=4 until @.d**2>k; if k//@.d==0 then iterate k
end /*d*/
#= # + 1; !.k= #; @.#= k /*found a prime, bump counter; assign @*/
end /*k*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
smooth: procedure expose @. !. #.; parse arg y,p /*obtain the arguments from the invoker*/
if p=='' then p= 3 /*Not specified? Then assume Hamming #s*/
n= !.p /*the number of primes being used. */
nn= n - 1; #.= 0; #.1= 1 /*an array of n-smooth numbers (so far)*/
f.= 1 /*the indices of factors of a number. */
do j=2 for y-1; _= f.1
z= @.1 * #._
do k=2 for nn; _= f.k; v= @.k * #._; if v<z then z= v
end /*k*/
#.j= z
do d=1 for n; _= f.d; if @.d * #._==z then f.d= f.d + 1
end /*d*/
end /*j*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
th: parse arg th; return th || word('th st nd rd', 1+(th//10)*(th//100%10\==1)*(th//10<4))
- output when using the default inputs:
════════════════════════════════════ a list of the 1st through 25th numbers for 2-smooth ═════════════════════════════════════ 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 ════════════════════════════════════ a list of the 1st through 25th numbers for 3-smooth ═════════════════════════════════════ 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 ════════════════════════════════════ a list of the 1st through 25th numbers for 5-smooth ═════════════════════════════════════ 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 ════════════════════════════════════ a list of the 1st through 25th numbers for 7-smooth ═════════════════════════════════════ 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 ════════════════════════════════════ a list of the 1st through 25th numbers for 11-smooth ════════════════════════════════════ 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 ════════════════════════════════════ a list of the 1st through 25th numbers for 13-smooth ════════════════════════════════════ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 ════════════════════════════════════ a list of the 1st through 25th numbers for 17-smooth ════════════════════════════════════ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 ════════════════════════════════════ a list of the 1st through 25th numbers for 19-smooth ════════════════════════════════════ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 ════════════════════════════════════ a list of the 1st through 25th numbers for 23-smooth ════════════════════════════════════ 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 ════════════════════════════════════ a list of the 1st through 25th numbers for 29-smooth ════════════════════════════════════ 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
- output when using the input of: 3000 3002 3 29
══════════════════════════════════ a list of the 3000th through 3002nd numbers for 3-smooth ══════════════════════════════════ 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 ══════════════════════════════════ a list of the 3000th through 3002nd numbers for 5-smooth ══════════════════════════════════ 278942752080 279936000000 281250000000 ══════════════════════════════════ a list of the 3000th through 3002nd numbers for 7-smooth ══════════════════════════════════ 50176000 50331648 50388480 ═════════════════════════════════ a list of the 3000th through 3002nd numbers for 11-smooth ══════════════════════════════════ 2112880 2116800 2117016 ═════════════════════════════════ a list of the 3000th through 3002nd numbers for 13-smooth ══════════════════════════════════ 390000 390390 390625 ═════════════════════════════════ a list of the 3000th through 3002nd numbers for 17-smooth ══════════════════════════════════ 145800 145860 146016 ═════════════════════════════════ a list of the 3000th through 3002nd numbers for 19-smooth ══════════════════════════════════ 74256 74358 74360 ═════════════════════════════════ a list of the 3000th through 3002nd numbers for 23-smooth ══════════════════════════════════ 46552 46575 46585 ═════════════════════════════════ a list of the 3000th through 3002nd numbers for 29-smooth ══════════════════════════════════ 33516 33524 33534
- output when using the input of: 30000 30019 503 521
════════════════════════════════ a list of the 30000th through 30019th numbers for 503-smooth ════════════════════════════════ 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 ════════════════════════════════ a list of the 30000th through 30019th numbers for 509-smooth ════════════════════════════════ 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 ════════════════════════════════ a list of the 30000th through 30019th numbers for 521-smooth ════════════════════════════════ 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
Ruby
def prime?(n) # P3 Prime Generator primality test
return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false
return false if n.gcd(6) != 1 # this filters out 2/3 of all integers
sqrtN = Integer.sqrt(n)
pc = -1 # initial P3 prime candidates value
until (pc += 6) > sqrtN # is resgroup 1st prime candidate > sqrtN
return false if n % pc == 0 || n % (pc + 2) == 0 # if n is composite
end
true
end
def gen_primes(a, b)
(a..b).select { |pc| pc if prime? pc }
end
def nsmooth(n, limit)
raise "Exception(n or limit)" if n < 2 || n > 521 || limit < 1
raise "Exception(must be a prime number: n)" unless prime? n
primes = gen_primes(2, n)
ns = [0] * limit
ns[0] = 1
nextp = primes[0..primes.index(n)]
indices = [0] * nextp.size
(1...limit).each do |m|
ns[m] = nextp.min
(0...indices.size).each do |i|
if ns[m] == nextp[i]
indices[i] += 1
nextp[i] = primes[i] * ns[indices[i]]
end
end
end
ns
end
gen_primes(2, 29).each do |prime|
print "The first 25 #{prime}-smooth numbers are: \n"
print nsmooth(prime, 25)
puts
end
puts
gen_primes(3, 29).each do |prime|
print "The 3000 to 3202 #{prime}-smooth numbers are: "
print nsmooth(prime, 3002)[2999..-1] # for ruby >= 2.6: (..)[2999..]
puts
end
puts
gen_primes(503, 521).each do |prime|
print "The 30,000 to 30,019 #{prime}-smooth numbers are: \n"
print nsmooth(prime, 30019)[29999..-1] # for ruby >= 2.6: (..)[29999..]
puts
end
- Output:
The first 25 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 25 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 25 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 25 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 25 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 25 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 25 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 25 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 25 23-smooth numbers are: [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] The first 25 29-smooth numbers are: [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] The 3000 to 3002 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3000 to 3002 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3000 to 3002 7-smooth numbers are: [50176000, 50331648, 50388480] The 3000 to 3002 11-smooth numbers are: [2112880, 2116800, 2117016] The 3000 to 3002 13-smooth numbers are: [390000, 390390, 390625] The 3000 to 3002 17-smooth numbers are: [145800, 145860, 146016] The 3000 to 3002 19-smooth numbers are: [74256, 74358, 74360] The 3000 to 3002 23-smooth numbers are: [46552, 46575, 46585] The 3000 to 3002 29-smooth numbers are: [33516, 33524, 33534] The 30,000 to 30,019 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000 to 30,019 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000 to 30,019 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Rust
fn is_prime(n: u32) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
if n % 3 == 0 {
return n == 3;
}
let mut p = 5;
while p * p <= n {
if n % p == 0 {
return false;
}
p += 2;
if n % p == 0 {
return false;
}
p += 4;
}
true
}
fn find_primes(from: u32, to: u32) -> Vec<u32> {
let mut primes: Vec<u32> = Vec::new();
for p in from..=to {
if is_prime(p) {
primes.push(p);
}
}
primes
}
fn find_nsmooth_numbers(n: u32, count: usize) -> Vec<u128> {
let primes = find_primes(2, n);
let num_primes = primes.len();
let mut result = Vec::with_capacity(count);
let mut queue = Vec::with_capacity(num_primes);
let mut index = Vec::with_capacity(num_primes);
for i in 0..num_primes {
index.push(0);
queue.push(primes[i] as u128);
}
result.push(1);
for i in 1..count {
for p in 0..num_primes {
if queue[p] == result[i - 1] {
index[p] += 1;
queue[p] = result[index[p]] * primes[p] as u128;
}
}
let mut min_index: usize = 0;
for p in 1..num_primes {
if queue[min_index] > queue[p] {
min_index = p;
}
}
result.push(queue[min_index]);
}
result
}
fn print_nsmooth_numbers(n: u32, begin: usize, count: usize) {
let numbers = find_nsmooth_numbers(n, begin + count);
print!("{}: {}", n, &numbers[begin]);
for i in 1..count {
print!(", {}", &numbers[begin + i]);
}
println!();
}
fn main() {
println!("First 25 n-smooth numbers for n = 2 -> 29:");
for n in 2..=29 {
if is_prime(n) {
print_nsmooth_numbers(n, 0, 25);
}
}
println!();
println!("3 n-smooth numbers starting from 3000th for n = 3 -> 29:");
for n in 3..=29 {
if is_prime(n) {
print_nsmooth_numbers(n, 2999, 3);
}
}
println!();
println!("20 n-smooth numbers starting from 30,000th for n = 503 -> 521:");
for n in 503..=521 {
if is_prime(n) {
print_nsmooth_numbers(n, 29999, 20);
}
}
}
- Output:
First 25 n-smooth numbers for n = 2 -> 29: 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216 3: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192 5: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54 7: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36 11: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32 13: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28 17: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27 19: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26 23: 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 29: 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 3 n-smooth numbers starting from 3000th for n = 3 -> 29: 3: 91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928 5: 278942752080, 279936000000, 281250000000 7: 50176000, 50331648, 50388480 11: 2112880, 2116800, 2117016 13: 390000, 390390, 390625 17: 145800, 145860, 146016 19: 74256, 74358, 74360 23: 46552, 46575, 46585 29: 33516, 33524, 33534 20 n-smooth numbers starting from 30,000th for n = 503 -> 521: 503: 62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964 509: 62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646 521: 62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336
Sidef
func smooth_generator(primes) {
var s = primes.len.of { [1] }
{
var n = s.map { .first }.min
{ |i|
s[i].shift if (s[i][0] == n)
s[i] << (n * primes[i])
} * primes.len
n
}
}
for p in (primes(2,29)) {
var g = smooth_generator(p.primes)
say ("First 25 #{'%2d'%p}-smooth numbers: ", 25.of { g.run }.join(' '))
}
say ''
for p in (primes(3,29)) {
var g = smooth_generator(p.primes)
say ("3,000th through 3,002nd #{'%2d'%p}-smooth numbers: ", 3002.of { g.run }.last(3).join(' '))
}
- Output:
First 25 2-smooth numbers: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 First 25 3-smooth numbers: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 First 25 5-smooth numbers: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 First 25 7-smooth numbers: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 First 25 11-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 First 25 13-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 First 25 17-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 First 25 19-smooth numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 First 25 23-smooth numbers: 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 First 25 29-smooth numbers: 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 3,000th through 3,002nd 3-smooth numbers: 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 3,000th through 3,002nd 5-smooth numbers: 278942752080 279936000000 281250000000 3,000th through 3,002nd 7-smooth numbers: 50176000 50331648 50388480 3,000th through 3,002nd 11-smooth numbers: 2112880 2116800 2117016 3,000th through 3,002nd 13-smooth numbers: 390000 390390 390625 3,000th through 3,002nd 17-smooth numbers: 145800 145860 146016 3,000th through 3,002nd 19-smooth numbers: 74256 74358 74360 3,000th through 3,002nd 23-smooth numbers: 46552 46575 46585 3,000th through 3,002nd 29-smooth numbers: 33516 33524 33534
Optionally, an efficient algorithm for checking if a given arbitrary large number is smooth over a given product of primes:
func is_smooth_over_prod(n, k) {
return true if (n == 1)
return false if (n <= 0)
for (var g = gcd(n,k); g > 1; g = gcd(n,k)) {
n /= g**valuation(n,g) # remove any divisibility by g
return true if (n == 1) # smooth if n == 1
}
return false
}
for p in (503, 509, 521) {
var k = p.primorial
var a = {|n| is_smooth_over_prod(n, k) }.first(30_019).last(20)
say ("30,000th through 30,019th #{p}-smooth numbers: ", a.join(' '))
}
- Output:
30,000th through 30,019th 503-smooth numbers: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 30,000th through 30,019th 509-smooth numbers: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 30,000th through 30,019th 521-smooth numbers: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
Swift
import BigInt
import Foundation
extension BinaryInteger {
@inlinable
public var isPrime: Bool {
if self == 0 || self == 1 {
return false
} else if self == 2 {
return true
}
let max = Self(ceil((Double(self).squareRoot())))
for i in stride(from: 2, through: max, by: 1) {
if self % i == 0 {
return false
}
}
return true
}
}
@inlinable
public func smoothN<T: BinaryInteger>(n: T, count: Int) -> [T] {
let primes = stride(from: 2, to: n + 1, by: 1).filter({ $0.isPrime })
var next = primes
var indices = [Int](repeating: 0, count: primes.count)
var res = [T](repeating: 0, count: count)
res[0] = 1
guard count > 1 else {
return res
}
for m in 1..<count {
res[m] = next.min()!
for i in 0..<indices.count where res[m] == next[i] {
indices[i] += 1
next[i] = primes[i] * res[indices[i]]
}
}
return res
}
for n in 2...29 where n.isPrime {
print("The first 25 \(n)-smooth numbers are: \(smoothN(n: n, count: 25))")
}
print()
for n in 3...29 where n.isPrime {
print("The 3000...3002 \(n)-smooth numbers are: \(smoothN(n: BigInt(n), count: 3002).dropFirst(2999).prefix(3))")
}
print()
for n in 503...521 where n.isPrime {
print("The 30,000...30,019 \(n)-smooth numbers are: \(smoothN(n: BigInt(n), count: 30_019).dropFirst(29999).prefix(20))")
}
- Output:
The first 25 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 25 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 25 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 25 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 25 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 25 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 25 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 25 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 25 23-smooth numbers are: [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] The first 25 29-smooth numbers are: [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] The 3000...3002 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3000...3002 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3000...3002 7-smooth numbers are: [50176000, 50331648, 50388480] The 3000...3002 11-smooth numbers are: [2112880, 2116800, 2117016] The 3000...3002 13-smooth numbers are: [390000, 390390, 390625] The 3000...3002 17-smooth numbers are: [145800, 145860, 146016] The 3000...3002 19-smooth numbers are: [74256, 74358, 74360] The 3000...3002 23-smooth numbers are: [46552, 46575, 46585] The 3000...3002 29-smooth numbers are: [33516, 33524, 33534] The 30,000...30,019 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000...30,019 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000...30,019 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
Wren
import "/math" for Int
import "/big" for BigInt, BigInts
// cache all primes up to 521
var smallPrimes = Int.primeSieve(521)
var primes = smallPrimes.map { |p| BigInt.new(p) }.toList
var nSmooth = Fn.new { |n, size|
if (n < 2 || n > 521) Fiber.abort("n must be between 2 and 521")
if (size < 1) Fiber.abort("size must be at least 1")
var bn = BigInt.new(n)
var ok = false
for (prime in primes) {
if (bn == prime) {
ok = true
break
}
}
if (!ok) Fiber.abort("n must be a prime number")
var ns = List.filled(size, null)
ns[0] = BigInt.one
var next = []
for (i in 0...primes.count) {
if (primes[i] > bn) break
next.add(primes[i])
}
var indices = List.filled(next.count, 0)
for (m in 1...size) {
ns[m] = BigInts.min(next)
for (i in 0...indices.count) {
if (ns[m] == next[i]) {
indices[i] = indices[i] + 1
next[i] = primes[i] * ns[indices[i]]
}
}
}
return ns
}
smallPrimes = smallPrimes.where { |p| p <= 29 }
for (i in smallPrimes) {
System.print("The first 25 %(i)-smooth numbers are:")
System.print(nSmooth.call(i, 25))
System.print()
}
for (i in smallPrimes.skip(1)) {
System.print("The 3,000th to 3,202nd %(i)-smooth numbers are:")
System.print(nSmooth.call(i, 3002)[2999..-1])
System.print()
}
for (i in [503, 509, 521]) {
System.print("The 30,000th to 30,019th %(i)-smooth numbers are:")
System.print(nSmooth.call(i, 30019)[29999..-1])
System.print()
}- Output:
The first 25 2-smooth numbers are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216] The first 25 3-smooth numbers are: [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192] The first 25 5-smooth numbers are: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54] The first 25 7-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36] The first 25 11-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 27, 28, 30, 32] The first 25 13-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28] The first 25 17-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27] The first 25 19-smooth numbers are: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26] The first 25 23-smooth numbers are: [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] The first 25 29-smooth numbers are: [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] The 3,000th to 3,202nd 3-smooth numbers are: [91580367978306252441724649472, 92829823186414819915547541504, 94096325042746502515294076928] The 3,000th to 3,202nd 5-smooth numbers are: [278942752080, 279936000000, 281250000000] The 3,000th to 3,202nd 7-smooth numbers are: [50176000, 50331648, 50388480] The 3,000th to 3,202nd 11-smooth numbers are: [2112880, 2116800, 2117016] The 3,000th to 3,202nd 13-smooth numbers are: [390000, 390390, 390625] The 3,000th to 3,202nd 17-smooth numbers are: [145800, 145860, 146016] The 3,000th to 3,202nd 19-smooth numbers are: [74256, 74358, 74360] The 3,000th to 3,202nd 23-smooth numbers are: [46552, 46575, 46585] The 3,000th to 3,202nd 29-smooth numbers are: [33516, 33524, 33534] The 30,000th to 30,019th 503-smooth numbers are: [62913, 62914, 62916, 62918, 62920, 62923, 62926, 62928, 62930, 62933, 62935, 62937, 62944, 62946, 62951, 62952, 62953, 62957, 62959, 62964] The 30,000th to 30,019th 509-smooth numbers are: [62601, 62602, 62604, 62607, 62608, 62609, 62611, 62618, 62620, 62622, 62624, 62625, 62626, 62628, 62629, 62634, 62640, 62643, 62645, 62646] The 30,000th to 30,019th 521-smooth numbers are: [62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]
zkl
GNU Multiple Precision Arithmetic Library and primes
var [const] BI=Import("zklBigNum"); // libGMP
fcn nSmooth(n,sz){ // --> List of big ints
if(sz<1) throw(Exception.ValueError("size must be at least 1"));
bn,primes,ns := BI(n), List(), List.createLong(sz);
if(not bn.probablyPrime()) throw(Exception.ValueError("n must be prime"));
p:=BI(1); while(p<n){ primes.append(p.nextPrime().copy()) } // includes n
ns.append(BI(1));
next:=primes.copy();
if(Void!=( z:=primes.find(bn)) ) next.del(z+1,*);
indices:=List.createLong(next.len(),0);
do(sz-1){
ns.append( nm:=BI( next.reduce(fcn(a,b){ a.min(b) }) ));
foreach i in (indices.len()){
if(nm==next[i]){
indices[i]+=1;
next[i]=primes[i]*ns[indices[i]];
}
}
}
ns
}smallPrimes:=List();
p:=BI(1); while(p<29) { smallPrimes.append(p.nextPrime().toInt()) }
foreach p in (smallPrimes){
println("The first 25 %d-smooth numbers are:".fmt(p));
println(nSmooth(p,25).concat(" "), "\n")
}
foreach p in (smallPrimes[1,*]){
print("The 3,000th to 3,202nd %d-smooth numbers are: ".fmt(p));
println(nSmooth(p,3002)[2999,*].concat(" "));
}
foreach p in (T(503,509,521)){
println("\nThe 30,000th to 30,019th %d-smooth numbers are:".fmt(p));
println(nSmooth(p,30019)[29999,*].concat(" "));
}- Output:
The first 25 2-smooth numbers are: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 The first 25 3-smooth numbers are: 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96 108 128 144 162 192 The first 25 5-smooth numbers are: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 The first 25 7-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 The first 25 11-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 18 20 21 22 24 25 27 28 30 32 The first 25 13-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 20 21 22 24 25 26 27 28 The first 25 17-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 24 25 26 27 The first 25 19-smooth numbers are: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 The first 25 23-smooth numbers are: 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 The first 25 29-smooth numbers are: 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 The 3,000th to 3,202nd 3-smooth numbers are: 91580367978306252441724649472 92829823186414819915547541504 94096325042746502515294076928 The 3,000th to 3,202nd 5-smooth numbers are: 278942752080 279936000000 281250000000 The 3,000th to 3,202nd 7-smooth numbers are: 50176000 50331648 50388480 The 3,000th to 3,202nd 11-smooth numbers are: 2112880 2116800 2117016 The 3,000th to 3,202nd 13-smooth numbers are: 390000 390390 390625 The 3,000th to 3,202nd 17-smooth numbers are: 145800 145860 146016 The 3,000th to 3,202nd 19-smooth numbers are: 74256 74358 74360 The 3,000th to 3,202nd 23-smooth numbers are: 46552 46575 46585 The 3,000th to 3,202nd 29-smooth numbers are: 33516 33524 33534 The 30,000th to 30,019th 503-smooth numbers are: 62913 62914 62916 62918 62920 62923 62926 62928 62930 62933 62935 62937 62944 62946 62951 62952 62953 62957 62959 62964 The 30,000th to 30,019th 509-smooth numbers are: 62601 62602 62604 62607 62608 62609 62611 62618 62620 62622 62624 62625 62626 62628 62629 62634 62640 62643 62645 62646 The 30,000th to 30,019th 521-smooth numbers are: 62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336
Categories:
- Programming Tasks
- Prime Numbers
- 11l
- C
- GMP
- C++
- C sharp
- Crystal
- D
- Delphi
- System.SysUtils
- System.Generics.Collections
- Velthuis.BigIntegers
- Factor
- Go
- Haskell
- J
- Java
- JavaScript
- Julia
- Kotlin
- Mathematica
- Wolfram Language
- Nim
- Bignum
- PARI/GP
- Pascal
- Perl
- Ntheory
- Phix
- Phix/mpfr
- Python
- Quackery
- Raku
- REXX
- Ruby
- Rust
- Sidef
- Swift
- AttaSwift BigInt
- Wren
- Wren-math
- Wren-big
- Zkl