0 like 0 dislike
0 like 0 dislike
Is there an efficient way to generate these numbers?

3 Answers

0 like 0 dislike
0 like 0 dislike
So you want all n=2·3^(a)·5^(b)·7^(c)·... where a,b,c,...∈{0,1} and n<N.

I'd suggest: Start with S[1]={2}, and iterate with

S[n+1] = S[n] ∪ {p[n]·x : x∈S[n] ∧ p[n]·x < N}

where the p[i] are the primes between 3 and √N inclusive.

IOW, given the set of numbers which are even, square-free, and have only prime factors less than or equal to p[k], multiply each number in the set (in increasing order) by p[k+1], terminating if you reach a value greater than or equal to N. Repeat until you run out of primes.

Initially, the set will double in size at each step: {2}, {2,6}, {2,6,10,30}, {2,6,10,14,30,42,70,210}, etc. Eventually you'll start getting numbers greater than or equal to N and the growth will slow down.
by
0 like 0 dislike
0 like 0 dislike
I can propose the following method but I'm not sure about the quick part...

So you start with 1 and iterate through the primes 3 <= p <= sqrt(n): for all products already computed, you add in the term p \* product if p \* product <= n / 2. You can sort the products after each iteration so you can stop early. Finally you multiply all the terms by 2 to make them even.
0 like 0 dislike
0 like 0 dislike
depending on the size of your numbers it would take the longest to calculate the square roots of the numbers, but it could also take a long time to multiply the primes as you go higher and higher it kinda looks like a bastardized factorial.

luckily there arent a whole lot of primes, so i guess you could make a database of them up to maybe 10^10 as i’m sure they are probably all found? that would speed up things significantly as you could iterate through those to multiply instead of having to calculate in real time each one lower than n for every input of n

edit: I believe i forgot how massive 10^10 is. this could not work depending on how many primes there are. the computational power needed would be quite huge

Related questions

0 like 0 dislike
0 like 0 dislike
1 answer
MSR_Tlse asked Jun 21
Are the S3/S4 Edexcel Further Maths units useful to become an actuary? Topics include sampling, unbiased and biased estimators, confidence intervals and significance test...
MSR_Tlse asked Jun 21
0 like 0 dislike
0 like 0 dislike
26 answers
ShanePaulNeil asked Jun 21
Why is it boring to be an actuary?
ShanePaulNeil asked Jun 21
0 like 0 dislike
0 like 0 dislike
7 answers
alfonsoesparzao asked Jun 21
Using SOA suggested text books to study for an exam
alfonsoesparzao asked Jun 21
0 like 0 dislike
0 like 0 dislike
3 answers
Pinterest_ITA asked Jun 21
Relative to LTAM, what would you guess is an appropriate difficulty multiplier for FAM-L ?
Pinterest_ITA asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
ANCJHB asked Jun 21
When to start exams/modules as an EL
ANCJHB asked Jun 21
by ANCJHB

29.6k questions

121k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!