Math Terminology Questions

[Robert_S]

So, I'm learning the Python programming language and was doing the standard exercise of testing for primeness and listing all the primes from here to there and that got me thinking about the composites and their relationship to the primes which led to looking for interesting patterns in the output my little scripts generate and also on the web.

I found that I lack in terminology when it comes to maths, so I'm asking here as things come up.


What is the term for how many primes a number can be divided by?

What is the term for how many primes and non primes a number can be divided by and the ratio of the two?

I noticed that if a number is divisible by a large amount of other numbers, a prime number can often be found a prime number of numbers up or down from it.* How do I express this in a less confusing way? Has someone else come up with a name for this?


This program I'm going to write will take smallish primes at random and keep multiplying them together until the heap is as high as 3 million or so, then I'll call the number Compost, then test for primeness in the numbers I get by adding or subtracting prime numbers to and from Compost.

Is there a name for this kind of algorithm?



*I think this is related to Euclid's(?) proof of the infinitude of primes. Don't tell me how though, I want to figure it out.

[JimC]

An interesting question, Robert. Without being specific about the terminology, I am going to do a cut and paste of an introduction to a project on primes and factors that I give to my advanced maths students. It is really about finding the total number of factors a composite number has, which masy only have a peripheral bearing on your issues...

In this area of mathematics, we are only interested in the natural numbers (positive whole numbers from one upwards). Prime numbers (2, 3, 5, 7 etc.) are natural numbers whose only factors are one and themselves. Composite numbers have at least one pair of factors other than one and themselves. If m is a composite number, then it can be written as a product:
m = a x b
where a and b are numbers greater than 1 and less than m
To find whether a number is prime, we need to try dividing it by prime numbers smaller than itself. Here is a useful shortcut – first find an approximate square root of the number. For example, 89

This means that we need only try to divide 89 by prime numbers smaller than 9 (so, 2, 3, 5, 7) Since 89 cannot be divided by any of these, it is a prime number.
Prime Factors
We can write any number as a product of its prime factors. This process is called prime decomposition. If there is more than one of a particular prime factor, it is usually written in index form. Also, the smaller primes are always written first. Examples:
77 = 7 x 11
72 = 8 x 9
= 2 x 2 x 2 x 3 x 3

= 23 x 32

2000 = 16 x 25

= 24 x 52

Repeated division, starting with the smallest possible prime, is a sensible method for large numbers. For example, to find the prime factors of 1512
2 1512
2 756
2 378
3 189
3 63
3 21
7 7

1512 = 23 x 33 x 7

Total number of factors (Tn)

It can be important to know the total number of factors that can divide into a particular composite number (including one and itself). Sometimes we need to list them all out, but sometimes we only need to know how many there are. For small numbers, it is not hard to list them, and then count:
72 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72 So, 72 has a total of 12 factors.
This would be awkward and time consuming for large numbers. Fortunately, there is a short cut, which depends on first working out the prime factors, as shown earlier. We use a general formula:

If the prime factors of a certain number are an1 x bn2 x cn3...

Then:

Tn = (n1 + 1)(n2 +1)(n3 + 1)...

Let’s check 72, which can be written as 23 x 32

Tn = (3 + 1)(2 + 1) = 4 x 3 = 12 which is correct

[Ronja]

Bookmarking this... Thanks, Jim!

[Robert_S]

Thanks Jim.

I figured that there had to be an ever lowering top bound for factors to live in because if our candidate for primeness: X is not divisible by 2, then you eliminate all divisors in the top half, if 3, you eliminate the top 2/3rds... yielding a pattern of: Test for Y divisibility then, if negative, eliminate all numbers greater than or equal to (1/Y)X.

This program I'm going to write will take smallish primes at random and keep multiplying them together until the heap is as high as 3 million or so, then I'll call the number Compost, then test for primeness in the numbers I get by adding or subtracting prime numbers to and from Compost.

Is there a name for this kind of algorithm?



*I think this is related to Euclid's(?) proof of the infinitude of primes. Don't tell me how though, I want to figure it out.

Update: I'm renaming my Compost variable to c and writing this script it to exclude one or two lowish (say, less than 47) primes at random and call it P then test for primeness in C + p and C - p.

Inspiration came when looking at 2,000,016 with an impressive 118 factors, none of which are 13, and seeing 2,000,029 (+13) and 2,000,003 (-13) being prime.

[JimC]

Thanks Jim.

I figured that there had to be an ever lowering top bound for factors to live in because if our candidate for primeness: X is not divisible by 2, then you eliminate all divisors in the top half, if 3, you eliminate the top 2/3rds... yielding a pattern of: Test for Y divisibility then, if negative, eliminate all numbers greater than or equal to (1/Y)X.

This program I'm going to write will take smallish primes at random and keep multiplying them together until the heap is as high as 3 million or so, then I'll call the number Compost, then test for primeness in the numbers I get by adding or subtracting prime numbers to and from Compost.

Is there a name for this kind of algorithm?



*I think this is related to Euclid's(?) proof of the infinitude of primes. Don't tell me how though, I want to figure it out.

Update: I'm renaming my Compost variable to c and writing this script it to exclude one or two lowish (say, less than 47) primes at random and call it P then test for primeness in C + p and C - p.

Inspiration came when looking at 2,000,016 with an impressive 118 factors, none of which are 13, and seeing 2,000,029 (+13) and 2,000,003 (-13) being prime.

Keep us posted of your results. I like this form of experimental mathematics!

(but I have no programming skills to pursue them)

The problems I set my students after the introduction I posted earlier include finding, for example, the smallest number that has exactly 20 factors...

(bearing in mind that there are, of course, an infinite number of numbers that have 20 factors...)

[JOZeldenrust]

Thanks Jim.

I figured that there had to be an ever lowering top bound for factors to live in because if our candidate for primeness: X is not divisible by 2, then you eliminate all divisors in the top half, if 3, you eliminate the top 2/3rds... yielding a pattern of: Test for Y divisibility then, if negative, eliminate all numbers greater than or equal to (1/Y)X.

This program I'm going to write will take smallish primes at random and keep multiplying them together until the heap is as high as 3 million or so, then I'll call the number Compost, then test for primeness in the numbers I get by adding or subtracting prime numbers to and from Compost.

Is there a name for this kind of algorithm?



*I think this is related to Euclid's(?) proof of the infinitude of primes. Don't tell me how though, I want to figure it out.

Update: I'm renaming my Compost variable to c and writing this script it to exclude one or two lowish (say, less than 47) primes at random and call it P then test for primeness in C + p and C - p.

Inspiration came when looking at 2,000,016 with an impressive 118 factors, none of which are 13, and seeing 2,000,029 (+13) and 2,000,003 (-13) being prime.

Keep us posted of your results. I like this form of experimental mathematics!

(but I have no programming skills to pursue them)

The problems I set my students after the introduction I posted earlier include finding, for example, the smallest number that has exactly 20 factors...

(bearing in mind that there are, of course, an infinite number of numbers that have 20 factors...)

Isn't that just the product of the twenty smallest primes? 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 x 47 x 51 x 53 x 59 x 61 x 67 = 400,774,399,105,093,619,849,833,590

[Xamonas Chegwé]

Thanks Jim.

I figured that there had to be an ever lowering top bound for factors to live in because if our candidate for primeness: X is not divisible by 2, then you eliminate all divisors in the top half, if 3, you eliminate the top 2/3rds... yielding a pattern of: Test for Y divisibility then, if negative, eliminate all numbers greater than or equal to (1/Y)X.

This program I'm going to write will take smallish primes at random and keep multiplying them together until the heap is as high as 3 million or so, then I'll call the number Compost, then test for primeness in the numbers I get by adding or subtracting prime numbers to and from Compost.

Is there a name for this kind of algorithm?



*I think this is related to Euclid's(?) proof of the infinitude of primes. Don't tell me how though, I want to figure it out.

Update: I'm renaming my Compost variable to c and writing this script it to exclude one or two lowish (say, less than 47) primes at random and call it P then test for primeness in C + p and C - p.

Inspiration came when looking at 2,000,016 with an impressive 118 factors, none of which are 13, and seeing 2,000,029 (+13) and 2,000,003 (-13) being prime.

Keep us posted of your results. I like this form of experimental mathematics!

(but I have no programming skills to pursue them)

The problems I set my students after the introduction I posted earlier include finding, for example, the smallest number that has exactly 20 factors...

(bearing in mind that there are, of course, an infinite number of numbers that have 20 factors...)

Isn't that just the product of the twenty smallest primes? 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 x 47 x 51 x 53 x 59 x 61 x 67 = 400,774,399,105,093,619,849,833,590

Nope. 219 = 524,288: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16,384, 32,768, 65,536, 131,072, 262,144, 524,288 is a lot smaller.

[Xamonas Chegwé]

I think the smallest number with 20 factors is 240 = 24.31.51 - by Jim's formula Tn = (4 + 1)(1 + 1)(1 + 1) = 5 x 2 x 2 = 20. Can't be arsed to work them all out though!

[JOZeldenrust]

I think the smallest number with 20 factors is 240 = 24.31.51 - by Jim's formula Tn = (4 + 1)(1 + 1)(1 + 1) = 5 x 2 x 2 = 20. Can't be arsed to work them all out though!

1. 1 x 240
2. 2 x 120
3. 3 x 80
4. 4 x 60
5. 5 x 48
6. 6 x 40
7. 8 x 30
8. 10 x 24
9. 12 x 20
10. 15 x 16
11. 16 x 15
12. 20 x 12
13. 24 x 10
14. 30 x 8
15. 40 x 6
16. 48 x 5
17. 60 x 4
18. 80 x 3
19. 120 x 2
20. 240 x 1

I misunderstood the question, thinking it was about unique prime divisors. Thanks for clearing that up.

[Xamonas Chegwé]

I think the smallest number with 20 factors is 240 = 24.31.51 - by Jim's formula Tn = (4 + 1)(1 + 1)(1 + 1) = 5 x 2 x 2 = 20. Can't be arsed to work them all out though!

1. 1 x 240
2. 2 x 120
3. 3 x 80
4. 4 x 60
5. 5 x 48
6. 6 x 40
7. 8 x 30
8. 10 x 24
9. 12 x 20
10. 15 x 16
11. 16 x 15
12. 20 x 12
13. 24 x 10
14. 30 x 8
15. 40 x 6
16. 48 x 5
17. 60 x 4
18. 80 x 3
19. 120 x 2
20. 240 x 1

I misunderstood the question, thinking it was about unique prime divisors. Thanks for clearing that up. You're right, by the way. The next smallest number with 20 factors is 420 = 22.31.51.71

420 has 24 factors. (2 + 1)(1 + 1)(1 + 1)(1 + 1) = 3 x 2 x 2 x 2 = 24

The next smallest with 20 factors is 336 = 24.31.71

[JOZeldenrust]

I think the smallest number with 20 factors is 240 = 24.31.51 - by Jim's formula Tn = (4 + 1)(1 + 1)(1 + 1) = 5 x 2 x 2 = 20. Can't be arsed to work them all out though!

1. 1 x 240
2. 2 x 120
3. 3 x 80
4. 4 x 60
5. 5 x 48
6. 6 x 40
7. 8 x 30
8. 10 x 24
9. 12 x 20
10. 15 x 16
11. 16 x 15
12. 20 x 12
13. 24 x 10
14. 30 x 8
15. 40 x 6
16. 48 x 5
17. 60 x 4
18. 80 x 3
19. 120 x 2
20. 240 x 1

I misunderstood the question, thinking it was about unique prime divisors. Thanks for clearing that up. You're right, by the way. The next smallest number with 20 factors is 420 = 22.31.51.71

420 has 24 factors. (2 + 1)(1 + 1)(1 + 1)(1 + 1) = 3 x 2 x 2 x 2 = 24

The next smallest with 20 factors is 336 = 24.31.71

Found that out right after I posted it, hence the edit. Thanks for preserving my stupidity.

[JimC]

Doing well, guys!

This is the sort of maths problem I like to set for my Year 9 Advanced Maths lads. It is open ended, and part of the deal is that they have to discuss the methods that they use. The interesting thing is that the more factors the original number (the one that is the "number of factors", like 20) has, the harder it is to be sure you have found the smallest number that has that number of factors.

If I'm not stretching their abilities, and stretching them hard, I am not doing my job...

[Robert_S]

The interesting thing is that the more factors the original number (the one that is the "number of factors", like 20) has, the harder it is to be sure you have found the smallest number that has that number of factors.

There might be some method for testing that, something that the original numbers have in common, or that the non-original numbers have in common.

Or there might be a way of constructing this number.



Right now I'm having a problem with a function I wrote that works well from a command line but freezes up in a script.

Jim, what computer platform do you use?

[JimC]

The interesting thing is that the more factors the original number (the one that is the "number of factors", like 20) has, the harder it is to be sure you have found the smallest number that has that number of factors.

There might be some method for testing that, something that the original numbers have in common, or that the non-original numbers have in common.

Or there might be a way of constructing this number.



Right now I'm having a problem with a function I wrote that works well from a command line but freezes up in a script.

Jim, what computer platform do you use?

Very ordinary, Robert - a mid-range PC running Windows Vista, and IE for my browser. Many people on the forum will do an eye-roll at such a pedestrian choice...

I do no programming at all, though I can do some useful things with Excel using look-up tables and "if" formulae; that's about my limit.

Put your problem in the tech section, and one of our mavens like Pappa or klr might know... There is also the Programmer's Only thread...

[Robert_S]

If you were running Mac or Linux, you could do some interesting things with a small vocabulary in Python, Perl or other languages without having to install anything.

But I think you can do pretty much the same things with spreadsheets, which fall just a bit shy of being Turing complete because they complain about some of the more interesting kinds of loops. But the visual aid of the grid layout makes up for it in part. I've used them quite a bit, but never for anything financial.