The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

Is there an easy way to determine how many factors a number has?
Message #1 Posted by Don Shepherd on 2 July 2011, 8:09 p.m.

My student wanted to know. The classic way is to do the prime factorization for the number, take the exponent of each prime factor and add 1 to it and multiply these together, and the result is the number of factors that the original number has.

The 17b can do it easily in a solver equation:

nf=0xL(a:(n))+2+(i:2:g(a):1:if(mod(n:i)=0:if(i=a:1:2):0))

It works on the 17b, 17bii, and 17bii+, although it's much slower on the plus.

Edited: 2 July 2011, 9:45 p.m.

      
Re: Is there an easy way to determine how many factors a number has?
Message #2 Posted by Paul Dale on 2 July 2011, 9:46 p.m.,
in response to message #1 by Don Shepherd

I'm not aware of any and I believe that finding this is equivalent in difficult to factorising. I looked at adding this to the 34s firmware but didn't dig too deeply.

Once you have the prime factorisation, determining the factors is straightforward as you've pointed out.

- Pauli

      
No, there is not!
Message #3 Posted by Gerson W. Barbosa on 3 July 2011, 10:58 a.m.,
in response to message #1 by Don Shepherd

Otherwise there would be a an easy way to tell whether a number is prime or not. There are a number of interesting properties related to this, however. One of them states that perfect squares, and only them, have an odd number of divisors (more at OEIS). This is the basis for the optimized solution to the 100 doors problem (the following wp34s program will display the doors that will be open after the last pass).

001 LBL D
002 2
003 10^x
004 SQRT
005 FP?
006 SKIP 02
007 RCL L
008 PSE 10
009 DEC L
010 x<> L
011 x>1?
012 BACK 08
013 RTN
            
Re: No, there is not!
Message #4 Posted by Marcus von Cube, Germany on 3 July 2011, 2:13 p.m.,
in response to message #3 by Gerson W. Barbosa

Gerson, wouldn't it be much easier to just compute the squares from 1^2 to 10^2 instead of testing each integer if it is a square?

                  
Re: No, there is not!
Message #5 Posted by Gerson W. Barbosa on 3 July 2011, 2:30 p.m.,
in response to message #4 by Marcus von Cube, Germany

Yes, it would :-) And it would make for an extremely short wp34s program.

BTW at least a couple of optimized C solutions there follow that approach:

#include <stdio.h>

int main() { int i; for (i = 1; i * i <= 100; i++) printf("door %d open\n", i * i);

return 0; }

#include <iostream> //compiled with "Dev-C++" , from RaptorOne

int main() { for(int i=1; i*i<=100; i++) std::cout<<"Door "<<i*i<<" is open!"<<std::endl; }

A mathematical explanation, in Spanish:

http://gaussianos.com/el-problema-de-las-100-puertas-y-los-divisores-de-un-numero-natural/

Edited: 3 July 2011, 2:36 p.m.

                        
Re: No, there is not!
Message #6 Posted by Ángel Martin on 3 July 2011, 5:31 p.m.,
in response to message #5 by Gerson W. Barbosa

at last an explanation I can understand :-)

                        
Re: No, there is not!
Message #7 Posted by Gilles Carpentier on 4 July 2011, 10:14 a.m.,
in response to message #5 by Gerson W. Barbosa

lol... in RPL could be

"door " { 1 2 3 4 5 6 7 8 9 10 } SQ ADD " is open" ADD MSGBOX

      
Re: Is there an easy way to determine how many factors a number has?
Message #8 Posted by Gilles Carpentier on 4 July 2011, 9:17 a.m.,
in response to message #1 by Don Shepherd

On the 50G it's very easy, but it's a little cheating ;)

DIVIS SIZE


[ Return to Index | Top of Index ]

Go back to the main exhibit hall