My factor program...

Xyzzy · 2005-09-18, 02:50

It is very simplistic and inefficient, but I made it all by myself...

If you think this version is ugly, you should have seen the prototypes!

http://www.mersenneforum.org/cgi-bin/factor?12

You can do any number up to 1e15... Just replace the part at the end of the URL... The larger numbers take a while because the mersenneforum.org server is a bit slow, but locally the program runs almost instantly... 999999999999947 should be the slowest number since it is the highest prime (I think!) under 1e15...

This is my first "real" Perl program... I hope to make it better over time as I learn more... I already have a few ideas to simplify the code... Comments are welcome, both about the math and the code, but please don't give me too much of an answer because I like to learn as I go...

The hardest part I have had with Perl so far is getting used to variables that are not strictly typed... Also, since there are numerous ways to do everything it is a bit overwhelming at first...

The part of the program that prints out the answer is especially obtuse... I am going to rewrite that part using a hash I think...

Printing out just the factors is trivial... The bulk of the code is input validation and getting everything pretty printed...

Code:

#!/usr/bin/perl -w
use strict;
my $number = $ENV{ 'QUERY_STRING' };
my $maxtest = int ( $number ** ( 1 / 2 ) ) + 1;
my $candidate = 2;
my @array;
my ( $factor, $counter );
my ( $equalflag, $timesflag ) = ( 0, 0 );
print "Content-type: text/html\n\n<tt>";
if ( $number =~ /^-?\d+$/ && $number >= 1 && $number <= 1_000_000_000_000_000 ) {
	print $number;
	push @array, 1 if $number == 1;
	until ( $number == 1 || $candidate > $maxtest ) {
		if ( $number % $candidate == 0 ) {
			push @array, $candidate;
			$number /= $candidate;
		}
		else {
			$candidate++;
		}
	}
	push @array, $number if $candidate > $maxtest;
	if ( scalar ( @array ) == 1 ) {
		print "&nbsp;is prime!";
		shift @array;
	}
	else {
		until ( scalar ( @array ) <= 1 ) {
			$factor = shift @array;
			$counter = 1;
			for ( 0 .. scalar ( @array ) - 1 ) {
				$counter++ if $array[ $_ ] == $factor;
			}
			if ( $counter == 1 ) {
				print "&nbsp;=" if $equalflag == 0;
				print "&nbsp;&times;" if $timesflag != 0;
				print "&nbsp;$factor";
				$equalflag++;
				$timesflag++;
			}
			else {
				print "&nbsp;=" if $equalflag == 0;
				print "&nbsp;&times;" if $timesflag != 0;
				print "&nbsp;$factor<sup>$counter</sup>";
				$equalflag++;
				$timesflag++;
				for ( 1 .. $counter - 1 ) {
					shift @array;
				}
			}
		}
	}
	if ( scalar ( @array ) == 1 ) {
		print "&nbsp;&times;" if $timesflag != 0;
		print "&nbsp;$array[ 0 ]";
	}
}
else {
	print "Invalid input!";
}
print "</tt>\n";

Xyzzy · 2005-09-22, 02:00

New version that uses a hash... Possibly easier to read...

Code:

#!/usr/bin/perl -w
use strict;
my $x = $ENV{'QUERY_STRING'};
print "content-type: text/html\n\n<tt>";
if ($x !~ /^-?\d+$/ || $x < 1 || $x > 1e15) {
	print "Invalid input!</tt>\n";
	exit;
}
print int $x;
my %h;
my $y = int($x**(1/2))+1;
my $z = 2;
$h{$x} = 1 if $x == 1;
until ($z > $y || $x == 1) {
	if ($x % $z == 0) {
		$x /= $z;
		$h{$z}++;
	}
	else {
		$z++;
	}
}
$h{$x} = 1 if $z > $y;
my $k;
my $f = 0;
for $k (sort{$a <=> $b}(keys(%h))) {
	if ($h{$k} == 1 && scalar(keys(%h)) == 1) {
		print " is prime!</tt>\n";
		exit;
	}
	$f > 0 ? print "&nbsp;&times;" : print "&nbsp;=";
	print "&nbsp;$k";
	print "<sup>$h{$k}</sup>" if $h{$k} > 1;
	$f++;
}
print "</tt>\n";

Xyzzy · 2005-09-23, 02:23

I'm too timid to post in the math forum, so I'll post about today's program and a related math question here...

http://en.wikipedia.org/wiki/Masahiko_Fujiwara

Just for fun I tested this way farther than I should have, given that article indicates there is a proof that there are only those four numbers... The code sample below only tests from 1 to 10,000... You can easily adjust it to test whatever range you want...

It is a very simple program, of course, and not too efficient because I had to convert numbers to strings and back again a few times... I'm curious if there is a better way to do it...

I'm also curious what the proof is, and whether or not a simple guy like me could understand it... I couldn't find anything on Google about it and the integer sequence database didn't have it either... I submitted it to the database but I'm certain I messed up the entry form since they ask all sorts of hard questions about the proposed sequence...

I suppose some people might say you could invent any sequence if you try hard enough... Is there anything special about this one at all?

Code:

#!/usr/bin/perl -w
use strict;
my $i;
my $j;
for $i ( 1e0 .. 1e4 ) {
	my $sum = 0;
	for $j ( 1 .. length ( $i ) ) {
		$sum += substr ( $i, $j - 1, 1 );
	}
	print "$i\n" if $sum * scalar ( reverse $sum ) == $i;
}

marc · 2005-09-23, 04:52

It's not a proof but instead of checking if any number has the right property, look for numbers which multiply to give numbers with the property.

Some python code...

Code:

def fujiwara(n):
    for i in range(9*n + 1):
        j = int("".join(reversed(str(i))))

        if sum(int(d) for d in str(i*j)) == i:
            print i, j, i*j
        
if __name__ == "__main__":
    fujiwara(5)

If you want to find a number with n or less digits with the property, then we know the sum of its digits must be <= 9n. We can look at every number less than or equal to 9n and see if it can make a number with the property...

Numbers · 2005-09-23, 22:12

One interesting point about reversing the digits of a number, say xyz, is that xyz – zyx is a multiple of 9.

9271 – 1729 = 838 * 9
541 – 145 = 44 * 9
91 – 19 = 8 * 9

So we know that if you start with two numbers a and b whose difference is a multiple of 9, then a-b = 9x, and therefore ab = b² + 9bx. So the number you are looking for must have this form.

In the case of 1729, for example, b = 19, x = 8. So b² + 9bx = 361 + 1368 = 1729.

One other curious thing about this number is that 1368 = 19 * 72, the four digits that make up 1729.

Numbers · 2005-09-23, 22:34

You can of course do this the other way around, and express ab in terms of a, when ab = a² - 9ax. So the number you are looking for must also have this form.

This time we get that for 1729, for example, a = 91, x = 8. So a² - 9ax = 8281 - 6552 = 1729.

And now we get 6552 = 91 * 72, the four digits that make up 1729.

andi314 · 2005-09-30, 18:40

http://www.mersenneforum.org/cgi-bin/factor?1
1 is prime!

i think this statement is not quite true !!!

Xyzzy · 2005-09-30, 19:13

http://mathworld.wolfram.com/PrimeNumber.html

I am using the info in that link... I wasn't sure what to put for 1... Since 1 has been considered a prime in the past I figured I'd list it as a prime until I understood the rest of that article...

akruppa · 2005-09-30, 19:28

>Since 1 has been considered a prime in the past

It has? It should not have been...

A prime is a number that can only be written as products that involve exactly one non-unit. Numbers that can be written as a product involving more than one non-unit are composites. Units are never prime, and the units of the integers are 1 and -1.

Alex

philmoore · 2005-09-30, 21:12

Quote:

Originally Posted by akruppa

>Since 1 has been considered a prime in the past

It has? It should not have been...

A prime is a number that can only be written as products that involve exactly one non-unit. Numbers that can be written as a product involving more than one non-unit are composites. Units are never prime, and the units of the integers are 1 and -1.

Alex

Although this is the usual accepted definition now, Derrick Lehmer included 1 as a prime not so very long ago...

trilliwig · 2005-10-01, 10:48

http://primes.utm.edu/notes/faq/one.html does a pretty good job of explaining why it is useful to consider 1 as a member of a separate category.

Quote:

Originally Posted by Numbers

One interesting point about reversing the digits of a number, say xyz, is that xyz – zyx is a multiple of 9.

Or indeed, the difference of any permutation of the digits xyz.

2005-09-18, 02:50	#1
Xyzzy "Mike" Aug 2002 3·2,741 Posts	My factor program... It is very simplistic and inefficient, but I made it all by myself... If you think this version is ugly, you should have seen the prototypes! http://www.mersenneforum.org/cgi-bin/factor?12 You can do any number up to 1e15... Just replace the part at the end of the URL... The larger numbers take a while because the mersenneforum.org server is a bit slow, but locally the program runs almost instantly... 999999999999947 should be the slowest number since it is the highest prime (I think!) under 1e15... This is my first "real" Perl program... I hope to make it better over time as I learn more... I already have a few ideas to simplify the code... Comments are welcome, both about the math and the code, but please don't give me too much of an answer because I like to learn as I go... The hardest part I have had with Perl so far is getting used to variables that are not strictly typed... Also, since there are numerous ways to do everything it is a bit overwhelming at first... The part of the program that prints out the answer is especially obtuse... I am going to rewrite that part using a hash I think... Printing out just the factors is trivial... The bulk of the code is input validation and getting everything pretty printed... Code: #!/usr/bin/perl -w use strict; my $number = $ENV{ 'QUERY_STRING' }; my $maxtest = int ( $number ** ( 1 / 2 ) ) + 1; my $candidate = 2; my @array; my ( $factor, $counter ); my ( $equalflag, $timesflag ) = ( 0, 0 ); print "Content-type: text/html\n\n<tt>"; if ( $number =~ /^-?\d+$/ && $number >= 1 && $number <= 1_000_000_000_000_000 ) { print $number; push @array, 1 if $number == 1; until ( $number == 1 \|\| $candidate > $maxtest ) { if ( $number % $candidate == 0 ) { push @array, $candidate; $number /= $candidate; } else { $candidate++; } } push @array, $number if $candidate > $maxtest; if ( scalar ( @array ) == 1 ) { print " is prime!"; shift @array; } else { until ( scalar ( @array ) <= 1 ) { $factor = shift @array; $counter = 1; for ( 0 .. scalar ( @array ) - 1 ) { $counter++ if $array[ $_ ] == $factor; } if ( $counter == 1 ) { print " =" if $equalflag == 0; print " ×" if $timesflag != 0; print " $factor"; $equalflag++; $timesflag++; } else { print " =" if $equalflag == 0; print " ×" if $timesflag != 0; print " $factor<sup>$counter</sup>"; $equalflag++; $timesflag++; for ( 1 .. $counter - 1 ) { shift @array; } } } } if ( scalar ( @array ) == 1 ) { print " ×" if $timesflag != 0; print " $array[ 0 ]"; } } else { print "Invalid input!"; } print "</tt>\n";

2005-09-23, 02:23	#3
Xyzzy "Mike" Aug 2002 3·2,741 Posts	I'm too timid to post in the math forum, so I'll post about today's program and a related math question here... http://en.wikipedia.org/wiki/Masahiko_Fujiwara Just for fun I tested this way farther than I should have, given that article indicates there is a proof that there are only those four numbers... The code sample below only tests from 1 to 10,000... You can easily adjust it to test whatever range you want... It is a very simple program, of course, and not too efficient because I had to convert numbers to strings and back again a few times... I'm curious if there is a better way to do it... I'm also curious what the proof is, and whether or not a simple guy like me could understand it... I couldn't find anything on Google about it and the integer sequence database didn't have it either... I submitted it to the database but I'm certain I messed up the entry form since they ask all sorts of hard questions about the proposed sequence... I suppose some people might say you could invent any sequence if you try hard enough... Is there anything special about this one at all? Code: #!/usr/bin/perl -w use strict; my $i; my $j; for $i ( 1e0 .. 1e4 ) { my $sum = 0; for $j ( 1 .. length ( $i ) ) { $sum += substr ( $i, $j - 1, 1 ); } print "$i\n" if $sum * scalar ( reverse $sum ) == $i; }

2005-09-23, 04:52	#4
marc Jun 2004 UK 139 Posts	It's not a proof but instead of checking if any number has the right property, look for numbers which multiply to give numbers with the property. Some python code... Code: def fujiwara(n): for i in range(9n + 1): j = int("".join(reversed(str(i)))) if sum(int(d) for d in str(ij)) == i: print i, j, ij if __name__ == "__main__": fujiwara(5) If you want to find a number with n or less digits with the property, then we know the sum of its digits must be <= 9n. We can look at every number less than or equal to 9n and see if it can make a number with the property... Last fiddled with by marc on 2005-09-23 at 04:53*

2005-09-23, 22:34	#6
Numbers Jun 2005 Near Beetlegeuse 2²·97 Posts	You can of course do this the other way around, and express ab in terms of a, when ab = a² - 9ax. So the number you are looking for must also have this form. This time we get that for 1729, for example, a = 91, x = 8. So a² - 9ax = 8281 - 6552 = 1729. And now we get 6552 = 91 * 72, the four digits that make up 1729. Last fiddled with by Numbers on 2005-09-23 at 22:36

2005-09-30, 19:28	#9
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	>Since 1 has been considered a prime in the past It has? It should not have been... A prime is a number that can only be written as products that involve exactly one non-unit. Numbers that can be written as a product involving more than one non-unit are composites. Units are never prime, and the units of the integers are 1 and -1. Alex Last fiddled with by akruppa on 2005-09-30 at 19:29

2005-09-23, 22:12	#5
Numbers Jun 2005 Near Beetlegeuse 604₈ Posts	One interesting point about reversing the digits of a number, say xyz, is that xyz – zyx is a multiple of 9. 9271 – 1729 = 838 * 9 541 – 145 = 44 * 9 91 – 19 = 8 * 9 So we know that if you start with two numbers a and b whose difference is a multiple of 9, then a-b = 9x, and therefore ab = b² + 9bx. So the number you are looking for must have this form. In the case of 1729, for example, b = 19, x = 8. So b² + 9bx = 361 + 1368 = 1729. One other curious thing about this number is that 1368 = 19 * 72, the four digits that make up 1729.

2005-09-30, 18:40	#7
andi314 Nov 2002 2·37 Posts	http://www.mersenneforum.org/cgi-bin/factor?1 1 is prime! i think this statement is not quite true !!!

2005-09-30, 19:13	#8
Xyzzy "Mike" Aug 2002 10000000011111₂ Posts	http://mathworld.wolfram.com/PrimeNumber.html I am using the info in that link... I wasn't sure what to put for 1... Since 1 has been considered a prime in the past I figured I'd list it as a prime until I understood the rest of that article...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New program to fully factor with GMP-ECM	rogue	GMP-ECM	51	2009-06-01 12:53
C program to factor using GMP-ECM and msieve	lazy	GMP-ECM	6	2007-06-16 18:12
Program to factor F14	dsouza123	Programming	79	2006-01-23 11:42
Where I find the best program to it factor keys? I use AMD.	chrow	Factoring	5	2004-02-19 10:15
New program to test a single factor	dsouza123	Programming	6	2004-01-13 03:53