Factoring

[alexander]

Well, i bet you thought that this will be some hard question on factoring, but in reality it is not, all i'm trying to do is figure out the amount of divisors a number has, but trying to do so mathematically, and i got stuck, but firstly why, where and for what...

 

my original problem involves a guy who has a huge amount of mailboxes that are first all closed, then all he does is secod time when he passes by them, he opens every second mailbox, the third time he passes the mailboxes, he changes state of every third mailbox and so forth. I have to write a program to do this and give out the final result. Easy thought I, a friend of mine found an algorithm that this seems to follow. after doing it all out the regular dumb way, he figured out for 30 mailboxes which ones will be open, and which ones will be closed, then after investigating the numbers, he found out that the amount of divisors a number has, effects whether the state of the mailbox will remain the same, or will change at the end. All it turned out to be is if the final amount of (divisors - 1) is even the state of the mailbox will change, if it is odd, the state of the mail box will remain as is. But it will not save me any time in loops to do it the mathemagical way vs. the regular dumb way that many students in our class will take, as i will need to generate an array with a list of amounts of divisors in each number. I know there must be a mathemagical way of doing this, i spent a while on Google searching this, but many solutions, involving some code ones were either waaay too complex or involved things that i can't...

 

Just wondering, it would be nice to have a formula to cut the time though and make the program more efficient :( , oh and this is for the datastructures class, not elementary algebra, just to make it clear.

[Buffy]

Feel free to use the code I posted over in http://www.hypography.com/scienceforums/showthread.php?t=1410

Which does the brute force version. Might not help you with data structures, since I didn't get that far yet!

 

The numbers are a little off, but its useful to see the the numbers whiz by to show how random the answer is....

 

Cheers,

Buffy

[alexander]

yeah, nice C code, wish it was a bit spaced out, cuz its hard to read :( but aside from that its not a matter of actually writing a program, its a matter of finding a better way to do things, brute force is only a way out if there is no better way out, and i am still not convinced that there is no better way out of this, but Thanks Buffy :(

[C1ay]

Well, i bet you thought that this will be some hard question on factoring, but in reality it is not, all i'm trying to do is figure out the amount of divisors a number has, but trying to do so mathematically, and i got stuck, but firstly why, where and for what...

 

Just wondering, it would be nice to have a formula to cut the time though and make the program more efficient :( , oh and this is for the datastructures class, not elementary algebra, just to make it clear.

 

Everyone hunting for prime numbers wishes they had this mathemagical formula. Lots of people have literally hunted for centuries to find such a formula. Good luck

[Turtle]

Alexander said, ". All it turned out to be is if the final amount of (divisors - 1) is even the state of the mailbox will change, if it is odd, the state of the mail box will remain as is. " ___The probelm here is that there is strictly speaking, numbers always have an even number of divisors. When dividing, you have a dividend, a divisor, & a quotient(also you may have a remainder, but we want no remainder to find 'proper divisors'). The divisor & quotient constitute 1 pair of proper divisors, as do all proper divisors.

___The idea of finding a magical shortcut for factoring is another holy grail of number theory; it would do no less than destroy the currently most secure methods of encryption. Nonetheless, it is a noble pursuit. :(

[alexander]

yeah i figured that i can find the amount of divisors by doing the primary number factoring, I think my program should not take more than 15 - 20 lines.... just gotta figure it out

[Buffy]

yeah, nice C code, wish it was a bit spaced out, cuz its hard to read :( but aside from that its not a matter of actually writing a program, its a matter of finding a better way to do things, brute force is only a way out if there is no better way out, and i am still not convinced that there is no better way out of this.

Tee hee! A bunch of us would probably love it if you gurus on the "H Dev Team" would figure out how to keep the thread editor from eating our tabs.... Warning, its actually C++, so "cc" in unix may have problems with it. It does at least have the short cut of not bothering to check for divisors larger than n/2, but as C1ay and Turtle avere, dere ain't no short cuts unless you're the next Issac Newton....

 

Cheers,

Buffy

[C1ay]

The probelm here is that there is strictly speaking, numbers always have an even number of divisors.

 

Aren't perfect squares the exception since one of the divisors is itself, where counted only once, would yield an odd set?

[C1ay]

Tee hee! A bunch of us would probably love it if you gurus on the "H Dev Team" would figure out how to keep the thread editor from eating our tabs....

 

Do the

 tags work here to preserve formatting?
 
--- CODE Test with Buffy's code---
[code]
#define MAXCOUNTER 100
// if NUMBEROFDIVISORS = 0, print ALL numbers from 1 to MAXCOUNTER
// if NUMBEROFDIVISORS > 0, print ONLY numbers with that number of pairs of divisors
#define NUMBEROFDIVISORS 0
int main(int argc, char *argv[])
{
   int maxcounter = MAXCOUNTER;
   int numberofdivisors = NUMBEROFDIVISORS;
   int counter;
   int maxelements;
   int index;
   int remainder, divisor1, divisor2;
   int elements, sum, difference;
   if (argc > 1) maxcounter = atoi(argv[1]);
   if (argc > 2) numberofdivisors = atoi(argv[2]);
   printf("Running integer statistics from 1 to %d, with %d divisor pairsn",maxcounter,numberofdivisors);
   printf("%10st%10st%10st%10sn","counter","sum","difference","elements");
   for (counter=1;counter<=maxcounter;counter++) {
       maxelements=(int) floor(sqrt((double) counter));
       elements=0; sum=0;
           for (index=1; index<=maxelements; index++) {
               remainder = counter % index;
                   if (remainder == 0) {
                       divisor1 = counter / index;
                       divisor2 = index;
                       sum += (divisor1 + divisor2);
                       elements++;
                   }
           }
       difference = sum - counter;
       if (numberofdivisors == 0 || elements == numberofdivisors)
           printf("%10dt%10dt%10dt%10dn",counter,sum, difference, elements);
   }
   return 0;
}

[Buffy]

Well, I'm pretty handy with lots of languages (as fans have noticed), but I don't know squat about BBCode....Thanks for the tip C1ay!

 

alexander: in reviewing the code, the only c++isms are:

• the // comments. (cc will only recognize /* */ as comments)
  
• the "x+=y" -> "x=x+y
  
• can't initialize vars in declarations.
  

The rest should compile fine in just about anything, although you'll have to include:

 

#include <stdio.h>

#include <math.h>

 

at the top....

 

Cheers,

Buffy

[Qfwfq]

Buffy: an even shorter cut for not checking numers greater than the root of n: if(i*i <= n). Since you're performing the division anyway, it might be even better yet to terminate the loop when n/i < i.

 

For all: an improvement is to first find the prime factorization of a given n:

 

n = 2^a * 3^b * ... * p^z

 

then the number of divisors including n itself is (1 + a)(1 + :(...(1 + z).

 

Eratosthenes' sieve can be run for all numbers up to quite large ones in fairly brief times and this only needs to be done once, if you won't be needing even larger numbers. A quite optimized implementation I wrote years ago can handle all unsigned long values, providing 256 megs can be allocated. If several hundred million is enough for you, any old PC can handle it easily. I'll post my version when I can retrieve it, if anyone is interested; if you don't need very large numbers, there are many versions around including this one (for primes under 100) in PERL:

 

perl -le '(1x$_)!~/^(11+)1+$/ && print for 2..100'

 

Once you have an array of flags (prime/not prime) you can avoid a great part of the divisions. For each prime, repeat n/p until n%p and the count gives you the multiplicity of that prime in n. Then retrieve the last remainderless quotient and re-iterate for the next prime, until you have exhausted n!!! :(

 

As Turtle may have gathered by now, I just simply adore prime numbers!!!

[alexander]

Dont worry buffy, i'm sure i can figure out how to work the code :( bottom line, i'll have to use g++ instead of gcc...

here's what i'm thinking of so far for the factor determining operation (i just have to think of it myself, i'll be cheating if i use someone elses code...(and i know it is reinventing the wheel, but it doesnt depend on what i think)):

//this should give you an array with all possible prime factors :( num is the number to get factored

*factors=new int[num];
int i=0, factor;

while(1)
{
   i++;
   for (factor=1; num%factor==0; factor++)
   {
       if(factor==10)
       {
           break;
       }
   }
   if(factor==10)
   {
       break;
   }
   else
   {
       num=num/factor;
       factors[i]=factor;
   }
}
i++;
// this will have an array of factors, but dont forget about the final value of num
factors[i]=num;
// now factors contains all factors that when multiplied by each other will give you the original number, at least i hope so...

[TeleMad]

... this is for the datastructures class ...

 

No one's attempt at a solution has yet to use a data structure (unless you count one person who used an array in one side aspect).

[Kent]

Hmm...... I have little patience to look through every post, but if the question is to fidn the number of factors in a number then it is quite easy.

 

Every number can be factored into a series of primes rise to a particular factor.

 

For example

 

let we have a number "36". How many divisors do 36 have?

 

We first represent it in to its primes

 

36=(2)(2)( 3)( 3)= (2^2)( 3^2)

 

You see the exponent 2 and 2?

 

add one to each exponent, and find their product. like this

 

 

(2+1)( 2+1)=9

 

9 is the number of divisors 36 has.

 

 

every number could be generalized like this

[Kent]

A question. Let N=(2^31)( 3^19)

 

How many Interger divisor of N^2 are less than N but do not divide N?

[alexander]

No one's attempt at a solution has yet to use a data structure (unless you count one person who used an array in one side aspect).

and what do you call this?

int *factors=new int[num];

excuse me if i'm wrong but i beleive i see a pointer to a dynamically allocated array in memory with no name...

[TeleMad]

and what do you call this?

int *factors=new int[num];

excuse me if i'm wrong but i beleive i see a pointer to a dynamically allocated array in memory with no name...

 

Excuse me, but what do you call this...

 

Telemad: ... (unless you count one person who used an array in one side aspect).

 

Oh, and data structures can have names, and where else would one allocate an array except in memory, and if you dynamically allocate an array wouldn't have a pointer anyway?

 

Now I can't speak for the instructor, but data structures are usually used to model the real world. Where' the mailbox in your code? I didn't see it.