HP49g+ inaccurate factoring

The Museum of HP Calculators

HP Forum Archive 16

HP49g+ inaccurate factoring
Message #1 Posted by Don Shepherd on 29 Jan 2007, 10:52 p.m.

I asked my HP49g+, my TI89 Titanium, and Mathematica to factor this number:
612123120220125942452052923312685765942
The HP did it in about 3 minutes, but got the wrong answer:
2 3^2 23 163 331 1721 63541 80287 3121351643366502743
The TI did it in about 5 minutes, and got the right answer:
2 3^2 23 163 331 1721 63541 80287 1089745801 2864293343
Mathematica got the same result as the TI (in less than 1 second!).
So the TI took longer, but got the right answer. Interesting. Can someone try this on the new 50g and see if gets the correct answer?

Re: HP49g+ inaccurate factoring
Message #2 Posted by Marcus von Cube, Germany on 30 Jan 2007, 3:35 a.m.,
in response to message #1 by Don Shepherd

Since the 49g+ and the 50g share the same firmware the results should be identical.
I just tried to factor 3121351643366502743. The 50g couldn't do it. The prime number algorithm uses "pseudo primes" which aren't always real prime numbers.

Re: HP49g+ inaccurate factoring
Message #3 Posted by Valentin Albillo on 30 Jan 2007, 7:36 a.m.,
in response to message #1 by Don Shepherd

Hi, Don:
For fun or for profit, you may want to check these factorizations o'mine, either with your calculator or with Mathematica. I've concocted them myself so it's highly unlikely you can find most of them anywhere. Nice "benchmark test" for a factorization program or device, right ? :-)

555555555555555555555555555555555551 = 31 * 431 * 35147009 * 1183041986955096880957199
77777777777777777777777777777777777777777777777771 = 89 * 181 * 3413 * 88085341 * 12586899513131 * 1275934133688965411653
555555555555554444444444444443333333333333332222222222222222211111111111111 = 3063441154048486369668261625739 * 181350163955772670068231705843686316121284149
100000000000020000000000000030000000000000000400000000000000050000000060000007 = 55197383 * 7331788879981 * 247099326407035913887379913393317654253759029551881897509
33333333333333333333333333333333333333333333333333333331 = 3995895244457 * 28439022012941 * 293325617460761101838340181063
19999999999999999999999999999999999999999999 = 14188750452331121 * 1409567394055769572492644719
199999999999999999999999999999999999999999999999999999999999 = 136541 * 3253850111311 * 8440450795922006821 * 53333947698860662675169
199999999999999999999999999999999999999999999999999999999999999999 = 57416791 * 5685045319 * 612713075321401087046458038954535213178204467231
888888888888888888888888888888888888887 = 922166778639871 * 963913371722125383063497
111111100111111111111011111111111111110111111111111111111 = 75339616691 * 2817029475925813 * 523531298049012572767508060617
1000000000000000500000000000000000000000000000000000001 = 128554033 * 1175279585285461 * 6618706171925367818957296251277
1000000000000000000000000000000000000000000000000000000000000000000000000000001 = 101 * 521 * 3121 * 9901 * 53397071018461 * 1900381976777332243781 * 6060517860310398033985611921721
7777777777777777777777777777777777777777777777777777777777777777777777777777777777771 = 4787299246700017 * 7991946870843910778647703 * 203288292027018362563164093122813459049537821
77777777777777777777777777777777777777777777777777777777777771 = 298684723 * 559035007 * 191656316854451 * 2430414671603628055773871371661
66666666666666666666666666666666666666666666666667 = 696005971439957313307 * 95784618814032449036431938481
6666666666666666666666666666666666666666666666666667 = 83117483 * 95748785401 * 17068764476981969 * 49077338018428921
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333331 = 5610682265465843 * 4029516254263034441 * 147438246840941109203773621095745543266780078120850988522768916325766488068008681432762749033715737
333333333333333333333333333333333333333333333333333333333333333333333333333333333337 = 9880106273 * 3549688971767 * 417800256562320935365459 * 22748780781841700495454793158537453973
7777777777777777777777777777777777777777777777777775777777777777777777777777777777777777 = 7078397 * 1592430035601737 * 690017735057724838853730820611220413502418136006617467351680032093
777777777777777777777777777777777777777777777777775777777777777777777777777777777777777777 = 611509954376459299030014869 * 912070930867832438835716332271 * 1394515626656963173831296487834723

Best regards from V.
Edited: 30 Jan 2007, 8:58 a.m.

Re: HP49g+ inaccurate factoring
Message #4 Posted by Don Shepherd on 30 Jan 2007, 9:05 a.m.,
in response to message #3 by Valentin Albillo

Thanks Valentin.
I'll try them when I get home after school today.
I love teaching math to 11-year-olds!!!
Don

Re: HP49g+ inaccurate factoring
Message #5 Posted by Don Shepherd on 30 Jan 2007, 9:33 p.m.,
in response to message #3 by Valentin Albillo

Hi Valentin.
Boy, those are some LARGE numbers you have there. I'm afraid that they overwhelm my calculators. In fact, all but the first two overwhelm Mathematica!
I'm curious as to how you created these. Unless you'd like to keep that info private, what hardware/software did you use to generate these?
thx, Don Shepherd

Re: HP49g+ inaccurate factoring
Message #6 Posted by Valentin Albillo on 31 Jan 2007, 11:16 a.m.,
in response to message #5 by Don Shepherd

Hi, Don:

It's not so much a matter of hardware and software as it is of algorithm selection. Matter of fact I did those using a run-of-the-mill P4 system @ 2.4 Ghz, 512 Mb RAM, under XP, in a MS Visual Studio development environment with the help of some multiprecision arithmetic library (to avoid reinventing the wheel). Nothing special there.
The key is the algorithm, which is no other but Lenstra's Elliptic Curve Factorization, which can routinely find factors of sizes up to 20 or 25 digits, with a 67-digit record as you may see in the reference. The largest first factor in my examples above is just 31 digits or so, which takes some time to find but can still be done in non-geological times.

Best regards from V.

Re: HP49g+ inaccurate factoring
Message #7 Posted by Don Shepherd on 31 Jan 2007, 10:39 p.m.,
in response to message #6 by Valentin Albillo

Thanks, Valentin.
I had read something about that factorization method at one time. Now you have sparked my interest again.
Don Shepherd

Re: HP49g+ inaccurate factoring
Message #8 Posted by Tim on 30 Jan 2007, 1:34 p.m.,
in response to message #1 by Don Shepherd

Hmm. . .
I did it on the 50G emulator that comes with debug4x and it did it in about 10 seconds. When I turned on real speed it behaved like the normal unit. Maybe there is a timeout issue.
TW

Re: HP49g+ inaccurate factoring
Message #9 Posted by Hal Bitton on 30 Jan 2007, 4:36 p.m.,
in response to message #8 by Tim

Do you suppose there is a software update for the 50g that addresses this issue?
Best regards, Hal

Re: HP49g+ inaccurate factoring
Message #10 Posted by Karl Schneider on 31 Jan 2007, 3:06 a.m.,
in response to message #1 by Don Shepherd

Hi, Don --

Quote:
I asked my HP49g+, my TI89 Titanium, and Mathematica to factor this number:
612123120220125942452052923312685765942
The HP did it in about 3 minutes, but got the wrong answer:
2 3^2 23 163 331 1721 63541 80287 3121351643366502743
The TI did it in about 5 minutes, and got the right answer:
2 3^2 23 163 331 1721 63541 80287 1089745801 2864293343
It seems that the HP-49G+ provided incomplete factorization, rather than incorrect factorization. I suspect that there might be a limit to the magnitude of factors obtained, in the interest of computational speed. That's just speculation, though.
Now for a surprise: The original HP-49G (mine with the last ROM version) provides the complete answer, although it took at least a half hour.
However, given the numerous examples of functions that worked fine on the HP-32SII, HP-17BII, and HP-12C but didn't make a fully-intact transition to the KinHPo successor models, maybe we shouldn't be astonished...
-- KS


Re: HP49g+ inaccurate factoring
Message #11 Posted by Marcus von Cube, Germany on 31 Jan 2007, 3:59 a.m.,
in response to message #10 by Karl Schneider

FACTOR(3121351643366502743) on the CAS of the HP 40gs returns the number unchanged. The machines share most of the CAS functions, the 40gs has just a different operating paradigm: The CAS works in the equation editor only. The algorithms are the same.
I just tried FACTOR(1089745801 x 2864293343). It returns 3121351643366502743. Funny, isn't it? No it's not!
A quote from Calcul formel et Mathematiques avec la HP49G en mode algebrique by Renée de Graeve:
Quote:
5.1.13 ISPRIME?
ISPRIME?(N) returns 1. (true) if N is pseudo-prime, and returns 0. (false) if N is not prime.
Definition: For all integers less than 10¹⁴ pseudo-primality and primality are the same! ...beyond 10¹⁴ a pseudo-prime integer has a very high probability to be prime (see the Rabin algorithm in section 7.6).
So, 3121351643366502743 has more than 14 digits and the pseudo prime algorithm simply regards it as "prime".
Marcus

Re: HP49g+ inaccurate factoring
Message #12 Posted by Vincent Perricone on 2 Feb 2007, 4:21 p.m.,
in response to message #1 by Don Shepherd

i Tried to do this with My HP 50G and Im not sure if I am doing this correctly but I type FACTOR(612123120220125942452052923312685765942), Which it automatically changes to 6.12XXXXXXXXXXXXXE38
what am I doing wrong.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall