cancel
Showing results for 
Search instead for 
Did you mean: 
cancel
Showing results for 
Search instead for 
Did you mean: 

Community Tip - You can Bookmark boards, posts or articles that you'd like to access again easily! X

Need help with creating a program function for "How many divisors does 20152016 have ?"

lvl107
20-Turquoise

Need help with creating a program function for "How many divisors does 20152016 have ?"

  Hello, Everyone.

  Need help with creating a program function for "How many divisors does 20152016 have ?"

     Thanks in advance for your time and help

         Regards.

ACCEPTED SOLUTION

Accepted Solutions
RichardJ
19-Tanzanite
(To:lvl107)

This gives all the proper factors of a number:

View solution in original post

18 REPLIES 18
RichardJ
19-Tanzanite
(To:lvl107)

This gives all the proper factors of a number:

Prime

divs.png

You only need the loop to go from 2 to floor(n/2). 1 and n are factors, but they are not proper factors (and can be easily added outside the loop if desired).

I thought those extra math symbols provided in Prime were just cosmetic. I didn't realize any of them actually "worked". I can't find anything about them in the help. Do you know if they all work, and if so what does a symbol such as "because" does?

RichardJ
19-Tanzanite
(To:RichardJ)

Actually, the loop only needs to go to floor(sqrt(n)), because once you have found one factor, it is obviously trivial to calculate another. This makes for a big improvement in speed for large numbers.

lvl107
20-Turquoise
(To:RichardJ)

  Many thanks for your time and help to my original post, Valery and Richard.

(1).PNG

           Best Regards.

               Loi.

RichardJ
19-Tanzanite
(To:lvl107)

It stands for exceeding the accuracy of the numeric computing in Mathcad. It won't work with a number that large. No more than 12 digits.

Where does 2^4-2 come from?

lvl107
20-Turquoise
(To:lvl107)

(2).PNG

   Is there an other way ? (for 2015201620162015)

       Best Regards.

Werner_E
25-Diamond I
(To:lvl107)

   Is there an other way ? (for 2015201620162015)

Yes. One could be to use symbolic eval instead of numeric, but I guess this will take a lot of time.

The second is this one as the mod-function seems to be a little more stable in this case. But I guess that sooner or later you will run into troubles with this method, too. After all the magnitude of numbers IS limited if you use the numerics.

Some remarks:

1) You will get a wrong result if x is a square of an integer as this routine then will count that integer twice. Should e easy to fix.

2) The usual convention in number theory is to add 1 and x to the list of divisors of a number. Even easier to fix.

3) As you just want to see the total number of divisors its not very efficient to create the whole vector (and then even sort it), just use a variable which counts. Should also be easy to implement.

4) As you probably know there is a much more efficient algorithm to get the number you want if we know the prime factors of x.

If the primefactorisation of x is

then the searched for number of different factors of x is

Example: 2015201620162015 is the product of four primes, as you have shown. So N=4 and each n.k is 1. The total number of factors (including 1, and x) therefore is (1+1)^4=16.


Unfortunately we do not have access to the results of the symbolic "factor" and so you would have to write your own routines which does the prime factorisation and counts how often each prime factor is used. You will run into numerical inaccuracies here, too, if x is big enough, I guess, so probably its not worth a try.


WE

Werner_E
25-Diamond I
(To:Werner_E)

You will run into numerical inaccuracies here, too, if x is big enough, I guess, so probably its not worth a try.

It may not be worth the effort, but it sure is a nice pastime.

So here is a routine using the algorithm described above.

I am pretty sure you could speed up the local routine f() which does the primefactorisation recursively using the usual methods (don't try divison by numbers already tried, make it iterative, use arrays with precalculated primes, ...)

But you sure run into numerical problems with slightly higher numbers:

So I was correct - not worth the effort 😉

WE

RichardJ
19-Tanzanite
(To:Werner_E)

The second is this one as the mod-function seems to be a little more stable in this case.

The limit of 12 digits is because "Use exact equality for comparisons and truncation" is unchecked in the worksheet options. Checking that would allow more digits, but at the risk of other numerical problems elsewhere in the worksheet. (From the help: "When not checked, the absolute value of the difference between two numbers divided by their average must be <10-12 for them to be considered equal, and only the first 12 decimal places are used in truncation."). Using the mod function is a good way to get around this.

1) You will get a wrong result if x is a square of an integer as this routine then will count that integer twice. Should e easy to fix.

Good catch. This fixes it:

2) The usual convention in number theory is to add 1 and x to the list of divisors of a number. Even easier to fix.

Well, I did say it calculated the proper factors. As you say, it is easy enough to add the trivial ones, but I'm not going to do it

Werner_E
25-Diamond I
(To:RichardJ)

Here's a shorter and iterative routine counting the number of factors.

Of course, as the last examples show, we run into the same numerical limitations.

Symbolic eval seems to run endless - I canceled calculation.

lvl107
20-Turquoise
(To:lvl107)

Unique Function .PNG

Relative query: 

Is it possible to create a program function for Unique Function with Input_Output as the above ? ( for Letter, Not number )

     Best Regards.

RichardJ
19-Tanzanite
(To:lvl107)

1). No. The factor keyword returns the number as the product of prime factors. Those are not all the factors (or even necessarily all the prime ones).

2). If the letters are strings, not undefined variable names:

This assumes the vector is sorted.

lvl107
20-Turquoise
(To:RichardJ)

  Thanks and ...thanks, Richard.

      Loi.

Richard Jackson написал(а):

You only need the loop to go from 2 to floor(n/2). 1 and n are factors, but they are not proper factors (and can be easily added outside the loop if desired).

I thought those extra math symbols provided in Prime were just cosmetic. I didn't realize any of them actually "worked". I can't find anything about them in the help. Do you know if they all work, and if so what does a symbol such as "because" does?

KISS - keep it simple...

Werner_E
25-Diamond I
(To:RichardJ)

I thought those extra math symbols provided in Prime were just cosmetic. I didn't realize any of them actually "worked". I can't find anything about them in the help. Do you know if they all work, and if so what does a symbol such as "because" does?

I guess Valery had misunderstood your question.

Unlike the "Because" symbol and others, which can be found in the "Symbols" palette and seem to be cosmetics only, the "Is Element Of" is a new operator and therefore is found in the "Operators" palette.

Werner

RichardJ
19-Tanzanite
(To:Werner_E)

I wasn't referring to the "Is Element Of" operator, but rather the "Z" used to represent the set of integers. We also have C, Q, and R. And the infinity symbol is also on that palette. However, I can answer my own question that the others are cosmetic only, including the various set operators. Except that under the currency symbols we have the Mathcad symbol for the unit of currency, which works as a unit, and the symbols for cent, GBP, Yen, and Euro (but, strangely, no $ symbol), which don't. IMO, mixing symbols that Mathcad recognizes and will interpret in some way with ones that are purely cosmetic is very confusing.

Werner_E
25-Diamond I
(To:RichardJ)

There are a bunch of things in Prime, which are confusing, so I am not really surprised.

Announcements

Top Tags