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 22 to 10610^6 and the program did it in 11 minute. Then I tried from 22 to 10910^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{red} box in the image is not important to be written now, you can assign variable k,lk,l and mm in there place, values of these variables will be different for different participants. I will talk about this later in the note.

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

The program will take all the natural numbers from ll to mm. 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 a0,a1,a2...aka_0,a_1,a_2...a_k where each list ana_n where nZn\in Z will be containing all the numbers having ''nn'' number of prime factors.

Whatweshallbedoing?\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,mk,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 xx;x=lmx\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!

Note by Zakir Husain
4 months, 2 weeks ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Log in to reply

Log in to reply

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

Aryan Sanghi - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

@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 - 4 months, 2 weeks ago

Log in to reply

@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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

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

Vinayak Srivastava - 4 months, 2 weeks ago

Log in to reply

@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.

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

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

Vinayak Srivastava - 4 months, 2 weeks ago

Log in to reply

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

Akela Chana - 4 months, 2 weeks ago

Log in to reply

@Akela Chana @Akela Chana - Added your name

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
//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);
}

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

''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 10910^9 I'm planning to try till 101210^{12} and after that 101510^{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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

Ok:)

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

But can you program this into Python version?

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

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

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

@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 - 4 months, 2 weeks ago

Log in to reply

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

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Aryan Sanghi - 4 months, 2 weeks ago

Log in to reply

Oic :)

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

@Zakir Husain Oh :)

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//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]);
}

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

It is arranged from smallest to largest :)

Jeff Giff - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

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 - 4 months, 2 weeks ago

Log in to reply

@David Stiff - Added your name

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

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

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

I am ready to co-operate! 🙂

Siddharth Chakravarty - 4 months, 2 weeks ago

Log in to reply

Thanks! Added you too.

Zakir Husain - 4 months, 2 weeks ago

Log in to reply

I don't know much about python, but I made a c++ code. There are limits, but I got the result for 10610^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 10610^6:

 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
26
27
28
29
30
78498
210035
250853
198062
124465
68963
35585
17572
8491
4016
1878
865
400
179
79
35
14
7
2
0
0
0
0
0
0
0
0
0
0
0

But your code says 864

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

 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
26
27
28
29
30
5761455
17427258
23727305
20959322
14371023
8493366
4600247
2367507
1180751
578154
279286
133862
63724
30143
14221
6644
3107
1430
661
297
133
62
25
11
4
1
0
0
0
0

Páll Márton (no activity) - 4 months, 1 week ago

Log in to reply

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

Páll Márton (no activity) - 4 months, 1 week ago

Log in to reply

BTW how can you connect computers to calculate this?

Páll Márton (no activity) - 4 months, 1 week ago

Log in to reply

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 - 4 months, 1 week ago

Log in to reply

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!

David Stiff - 4 months, 1 week ago

Log in to reply

 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
26
27
28
#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;
}

Páll Márton (no activity) - 4 months, 1 week ago

Log in to reply

@Páll Márton (no activity) Thanks Pall. I think I overestimated my code interpretation skills though. :)

David Stiff - 4 months, 1 week ago

Log in to reply

can you provide the code you used?

Zakir Husain - 4 months, 1 week ago

Log in to reply

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...