On Most common number of prime factor!

After seeing this note I made a python program to count number of prime factors of all the numbers from $2$ to $10^6$ and the program did it in $1$ minute. Then I tried from $2$ to $10^9$ but I calculated that it will take more than one day to complete the task.

Then I planned to organize an event to complete the task not alone but with other brilliant members! (so as to work faster)

Everyone who have a computer (or laptop) and have python IDLE or any IDE to write the program can participate.

What you have to do right now is the following :

Give you Brilliant username if you are interested so that I can organize everything accordingly.
Write the following program and save it till I instructs further :

The thing written in the $\red{red}$ box in the image is not important to be written now, you can assign variable $k,l$ and $m$ in there place, values of these variables will be different for different participants. I will talk about this later in the note.

$\large{What \quad the\quad program\quad does?}$

The program will take all the natural numbers from $l$ to $m$ . And then it shall be prime factorizing each of them and counting the number of prime factor each number will be having, and then it will be forming lists $a_0,a_1,a_2...a_k$ where each list $a_n$ where $n\in Z$ will be containing all the numbers having '' $n$ '' number of prime factors.

$\large{What\quad we \quad shall \quad be \quad doing?}$

We shall be running this program jointly, every Sunday (from 26 July) I will be sharing values of $k,l,m$ for each participant. What they have to do is to put these values in the program and then they have to run it, in output they have to give the commands :

for i in range(0,k): print(eval("len(a"+str(i)+")"))

The output that you will be getting shall be like this (just an example):

What you will be doing after this is to share the output you got here in the comments.

Every participants will get there task on Sunday and they can submit there outputs till the next Sunday comes.

Note :

There is no limit of number of participants, also you can submit your name on any date.
A request to RadMath community to add this in their ''Late Events''
If any confusion is their in your mind related to this event then clear it quickly here.
The time complexity of the program is about $x\sqrt{x};x=|l-m|$ . If you have any better program with lesser time complexity then kindly share here.
Any suggestions can be given in the comments below.
The event will start from 26 July, 2020
First week note
Hope we will explore something interesting and new!

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

//run this first to get the primes less than 1000000000 or change it to python and run int main { int p[3000000000]={2,3,5,7,11,13,17,19};//primes int i,num,head; head=8; printf(“2,3,5,7,11,13,17,19,”); for(num=20;num<=1000000000;num++) { for(i=0;p[i]*p[i]<num;i++) { if(num%p[i]=0) continue; } printf(“%d,”,num); }

//then run this (python version!) :) //time complexity:<O(n\sqrt{n})/3 int main { int num,k,numFactors[1000000000] int prime[300000000]={paste the output from the last program}; for(num=1;num<=1000000000;num++) for(k=0;prime[k]*prime[k]<=num;k++) if(p[k]%num==0) numFactors[num]++; for(k=0;k<=1000000000;k++) printf(“%d has %d prime factors \n”,k+1,numFactor[k]); }

#include <iostream> #include <vector> using namespace std; typedef long long int longint; vector<longint> first; vector<longint> second; vector<longint> solution; const longint minimum=2; longint maximum=1000000; int main() { first.resize(maximum+1,0); second.resize(maximum+1,0); for(int a=minimum;a<=maximum;a++){ if(second[a]==-1) continue; for(int b=a;b<=maximum;b+=a){ first[b]++; second[b]=(second[b]==-1)?-1:(second[b]==0)?a:(a%second[b]==0)?second[b]:-1; } } for(int a=minimum;a<=maximum;a++){ if(first[a]>=solution.size()) solution.resize(first[a]+1,0); solution[first[a]]++; } for(int a=1;a<solution.size();a++) cout << solution[a] << endl; return 0; }

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

@David Stiff, @Justin Travers, @Jeff Giff, @Vinayak Srivastava, @jordi curto, @Aryan Sanghi, @Yajat Shamji, @Kumudesh Ghosh, @Alak Bhattacharya, @Marvin Kalngan, I can't do it alone we must work together

Zakir Husain - 11 months, 1 week ago

@Mahdi Raza, @Kriti Kamal, @Laurent Verweijen, @Pop Wong, @Akela Chana, @Maria Paszkiewicz, @Sahar Bano, @L Chua, @Razing Thunder, @Hamza Anushath, @Adhiraj Dutta, @Gandoff Tan, Try if anyone can help!

Ok I am ready. Will try to find a better code. :) Username same as name.

Aryan Sanghi - 11 months, 1 week ago

Thanks! You are in. Will you also be participating for the task also? (Executing the code)

@Zakir Husain, Sir, sorry, but I am not good at coding, I only know some basic codes, so I may not be able to help. But if there is anything other than coding to be done, do tell me!

Vinayak Srivastava - 11 months, 1 week ago

@Vinayak Srivastava - No need to code, just execute the code in the image and as the instructions are given every Sunday (from 26 July) I myself will share the code. What you need to do is just execute it on your device and share the output

Ok, then I'll try. Please just tell me which software I need to download.

@Vinayak Srivastava – Just download Python 3.8 here (or you may use any other IDE to run the program) and search for ''IDLE'' in your device (after download) the code will be executed there. Don't try now, I will provide instructions for for now only do this much.

@Vinayak Srivastava – @Vinayak Srivastava - I will suggest you this video if you are new to ''IDLE''

@Zakir Husain – Oh, thanks! I'll watch it today.

Zakir I don't know much about codes. But i can run it on IDLE. Count me in. User name Akela.

Akela Chana - 11 months, 1 week ago

@Akela Chana – @Akela Chana - Added your name

Jeff Giff - 11 months, 1 week ago

''C'' have a limit in int type, this program will work till 2,147,483,647 but after going that far it may not work. What I will be doing is that we want more and more numbers. After going till $10^9$ I'm planning to try till $10^{12}$ and after that $10^{15}$ and so on (not alone but together). But thanks for the idea I will try on my device. Kindly mention this discussion in RedMaths

Ok:)

But can you program this into Python version?

@Jeff Giff – A program is given above also, but I can build a new one on your algorithm!

@Zakir Husain – By the way, is this for research? :)

@Jeff Giff – No, it's just for fun and enjoyment in math and to see if we can find something new and interesting in math which no one have ever seen!

@Zakir Husain – Hmmm... what about Twin numbers(two integers $a,b$ where the sum of the integer factors of $a$ excluding $a$ add up to $b$ , and also the other way round)?

It has $n\sqrt{n}$ time complexity. You could use Sieve Of Erasthoneses to find prime factors till $n$ in $nloglogn$ time complexity.

Oic :)

Wait... this is an improved version! The prime need only be less than $\sqrt{\text{number}}$ instead of the number itself.

So I tested every prime less than the square root of the number, so for a number n, the time complexity would be $\text{rate that a positive integer is prime}\times \sqrt{n}$ .

@Jeff Giff – But still it will be $\approx n\sqrt{n}$

@Zakir Husain – Oh :)

Nice method! But how will you arrange the data coming out, it will be a very huge data.

It is arranged from smallest to largest :)

@Jeff Giff - I've added your name as a participant too

I'm in. Username same as name.

Love the code by the way! I almost got it all, but I would love a more detailed explanation of how it works!

Not sure if generating a list of primes ahead of time has already been mentioned. Not sure if it would save time either.

I've never heard of the global() function, but I've always wanted to be able to generate variables with incrementing names. Thanks!

And thanks for taking such an interest in this. I didn't imagine the problem would be split up and solved communally! :)

David Stiff - 11 months, 1 week ago

@David Stiff - Added your name

List of participants (for clarification to all, a new note having all the information is coming soon!) :

I am ready to co-operate! 🙂

Siddharth Chakravarty - 11 months ago

Thanks! Added you too.

Zakir Husain - 11 months ago

I don't know much about python, but I made a c++ code. There are limits, but I got the result for $10^6$ in 0.358 seconds. Maybe your code is bad or your processor is old. I use AMD A4-4020 with Radeon(tm) HD Graphics 3.20 GHz. The result for $10^6$ :

But your code says 864

I can say the results only until $10^8$ , from $10^9$ the vectors size is too big, so the system can't use them :( The result for $10^8$ in 39.567 seconds:

A Former Brilliant Member - 11 months ago

Now I added to my code an auto sizer to get the result without zeros :)

BTW how can you connect computers to calculate this?

I believe the idea is to have multiple people calculate small intervals on their own, and then the results will be summed together.

David Stiff - 11 months ago

Hi Pall. Would you mind sharing your code? I'd be very interested in knowing how you did this in less than half a second! I don't know C++, but I could probably determine the basic idea behind it. Thanks!

@A Former Brilliant Member – Thanks Pall. I think I overestimated my code interpretation skills though. :)

can you provide the code you used?

New note : $\large{Number\quad Of\quad Prime\quad factor\quad (N.O.P.)\quad Week\quad 1}$

$\Large{Announcement:}$ New plan is here, everything is nearly changed now

Zakir Husain - 2 months, 3 weeks ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$