Page 2 of 3 FirstFirst 123 LastLast
Results 16 to 30 of 45

Math Help - Integer Solutions?

  1. #16
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    Thanks for the information about pari/gp. I wish I had the time to take a look at it.
    I've modified my k=4 solution finding program and it is now about *3 faster on my machine.
    As I'm currently only searching for fairly small solutions I've built a table of squares up front, so all the multiplications in the outer loops disappear.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Raw Data

    Hey guys, I found some more... If you just copy/paste the text below you should be able to put it in a spreadsheet easily enough. I'll post again with a run-through of my search algorithm.


    67405=1*1*5*13*17*61=227^2+126^2=218^2+141^2=189^2 +178^2=237^2+106^2 and (227*126)^2+(218*141)^2=(189*178)^2+(237*106)^2
    600445=1*1*5*29*41*101=613^2+474^2=773^2+54^2=683^ 2+366^2=206^2+747^2 and (613*474)^2+(773*54)^2=(683*366)^2+(206*747)^2
    55445869=1*1*37*37*101*401=1110^2+7363^2=3438^2+66 05^2=2062^2+7155^2=6915^2+2762^2 and (1110*7363)^2+(3438*6605)^2=(2062*7155)^2+(6915*27 62)^2
    242048509=1*1*53*73*73*857=14853^2+4630^2=14090^2+ 6597^2=8478^2+13045^2=15403^2+2190^2 and (14853*4630)^2+(14090*6597)^2=(8478*13045)^2+(1540 3*2190)^2
    5915065=1*5*13*17*53*101=2076^2+1267^2=2428^2+141^ 2=2324^2+717^2=2253^2+916^2 and (2076*1267)^2+(2428*141)^2=(2324*717)^2+(2253*916) ^2
    81524605=1*5*17*41*149*157=8498^2+3051^2=8629^2+26 58^2=7947^2+4286^2=9003^2+686^2 and (8498*3051)^2+(8629*2658)^2=(7947*4286)^2+(9003*68 6)^2
    532946005=1*5*17*53*281*421=19598^2+12201^2=20583^ 2+10454^2=21366^2+8743^2=17769^2+14738^2 and (19598*12201)^2+(20583*10454)^2=(21366*8743)^2+(17 769*14738)^2
    166045477=1*13*17*61*109*113=12606^2+2671^2=10609^ 2+7314^2=12351^2+3674^2=11199^2+6374^2 and (12606*2671)^2+(10609*7314)^2=(12351*3674)^2+(1119 9*6374)^2
    1685125=5*5*5*13*17*61=1135^2+630^2=1090^2+705^2=9 45^2+890^2=1185^2+530^2 and (1135*630)^2+(1090*705)^2=(945*890)^2+(1185*530)^2
    15011125=5*5*5*29*41*101=3065^2+2370^2=3865^2+270^ 2=3415^2+1830^2=1030^2+3735^2 and (3065*2370)^2+(3865*270)^2=(3415*1830)^2+(1030*373 5)^2
    1386146725=5*5*37*37*101*401=5550^2+36815^2=17190^ 2+33025^2=10310^2+35775^2=34575^2+13810^2 and (5550*36815)^2+(17190*33025)^2=(10310*35775)^2+(34 575*13810)^2
    6051212725=5*5*53*73*73*857=74265^2+23150^2=70450^ 2+32985^2=42390^2+65225^2=77015^2+10950^2 and (74265*23150)^2+(70450*32985)^2=(42390*65225)^2+(7 7015*10950)^2
    11391445=5*13*13*13*17*61=2951^2+1638^2=2834^2+183 3^2=2457^2+2314^2=3081^2+1378^2 and (2951*1638)^2+(2834*1833)^2=(2457*2314)^2+(3081*13 78)^2
    101475205=5*13*13*29*41*101=2678^2+9711^2=8879^2+4 758^2=10049^2+702^2=7969^2+6162^2 and (2678*9711)^2+(8879*4758)^2=(10049*702)^2+(7969*61 62)^2
    19480045=5*13*17*17*17*61=3859^2+2142^2=3706^2+239 7^2=3213^2+3026^2=4029^2+1802^2 and (3859*2142)^2+(3706*2397)^2=(3213*3026)^2+(4029*18 02)^2
    56687605=5*13*17*29*29*61=6583^2+3654^2=6322^2+408 9^2=5481^2+5162^2=6873^2+3074^2 and (6583*3654)^2+(6322*4089)^2=(5481*5162)^2+(6873*30 74)^2
    92277445=5*13*17*37*37*61=8399^2+4662^2=8066^2+521 7^2=6993^2+6586^2=8769^2+3922^2 and (8399*4662)^2+(8066*5217)^2=(6993*6586)^2+(8769*39 22)^2
    113307805=5*13*17*41*41*61=9307^2+5166^2=8938^2+57 81^2=7749^2+7298^2=9717^2+4346^2 and (9307*5166)^2+(8938*5781)^2=(7749*7298)^2+(9717*43 46)^2
    189340645=5*13*17*53*53*61=12031^2+6678^2=11554^2+ 7473^2=10017^2+9434^2=12561^2+5618^2 and (12031*6678)^2+(11554*7473)^2=(10017*9434)^2+(1256 1*5618)^2
    250814005=5*13*17*61*61*61=13847^2+7686^2=13298^2+ 8601^2=11529^2+10858^2=14457^2+6466^2 and (13847*7686)^2+(13298*8601)^2=(11529*10858)^2+(144 57*6466)^2
    359201245=5*13*17*61*73*73=16571^2+9198^2=15914^2+ 10293^2=13797^2+12994^2=17301^2+7738^2 and (16571*9198)^2+(15914*10293)^2=(13797*12994)^2+(17 301*7738)^2
    687598405=5*13*17*61*101*101=22927^2+12726^2=22018 ^2+14241^2=19089^2+17978^2=23937^2+10706^2 and (22927*12726)^2+(22018*14241)^2=(19089*17978)^2+(2 3937*10706)^2
    800838805=5*13*17*61*109*109=24743^2+13734^2=23762 ^2+15369^2=20601^2+19402^2=25833^2+11554^2 and (24743*13734)^2+(23762*15369)^2=(20601*19402)^2+(2 5833*11554)^2
    860694445=5*13*17*61*113*113=25651^2+14238^2=24634 ^2+15933^2=21357^2+20114^2=26781^2+11978^2 and (25651*14238)^2+(24634*15933)^2=(21357*20114)^2+(2 6781*11978)^2
    1496458405=5*13*17*61*149*149=33823^2+18774^2=3248 2^2+21009^2=28161^2+26522^2=35313^2+15794^2 and (33823*18774)^2+(32482*21009)^2=(28161*26522)^2+(3 5313*15794)^2
    1661465845=5*13*17*61*157*157=35639^2+19782^2=3422 6^2+22137^2=29673^2+27946^2=37209^2+16642^2 and (35639*19782)^2+(34226*22137)^2=(29673*27946)^2+(3 7209*16642)^2
    5322366205=5*13*17*61*281*281=63787^2+35406^2=6125 8^2+39621^2=53109^2+50018^2=66597^2+29786^2 and (63787*35406)^2+(61258*39621)^2=(53109*50018)^2+(6 6597*29786)^2
    10838791405=5*13*17*61*401*401=91027^2+50526^2=874 18^2+56541^2=75789^2+71378^2=95037^2+42506^2 and (91027*50526)^2+(87418*56541)^2=(75789*71378)^2+(9 5037*42506)^2
    11946929605=5*13*17*61*421*421=95567^2+53046^2=917 78^2+59361^2=79569^2+74938^2=99777^2+44626^2 and (95567*53046)^2+(91778*59361)^2=(79569*74938)^2+(9 9777*44626)^2
    49505534845=5*13*17*61*857*857=194539^2+107982^2=1 86826^2+120837^2=161973^2+152546^2=203109^2+90842^ 2 and (194539*107982)^2+(186826*120837)^2=(161973*152546 )^2+(203109*90842)^2
    173528605=5*17*17*29*41*101=10421^2+8058^2=13141^2 +918^2=11611^2+6222^2=3502^2+12699^2 and (10421*8058)^2+(13141*918)^2=(11611*6222)^2+(3502* 12699)^2
    504974245=5*29*29*29*41*101=17777^2+13746^2=22417^ 2+1566^2=19807^2+10614^2=5974^2+21663^2 and (17777*13746)^2+(22417*1566)^2=(19807*10614)^2+(59 74*21663)^2
    822009205=5*29*37*37*41*101=22681^2+17538^2=28601^ 2+1998^2=25271^2+13542^2=7622^2+27639^2 and (22681*17538)^2+(28601*1998)^2=(25271*13542)^2+(76 22*27639)^2
    1009348045=5*29*41*41*41*101=25133^2+19434^2=31693 ^2+2214^2=28003^2+15006^2=8446^2+30627^2 and (25133*19434)^2+(31693*2214)^2=(28003*15006)^2+(84 46*30627)^2
    1686650005=5*29*41*53*53*101=32489^2+25122^2=40969 ^2+2862^2=36199^2+19398^2=10918^2+39591^2 and (32489*25122)^2+(40969*2862)^2=(36199*19398)^2+(10 918*39591)^2
    2234255845=5*29*41*61*61*101=37393^2+28914^2=47153 ^2+3294^2=41663^2+22326^2=12566^2+45567^2 and (37393*28914)^2+(47153*3294)^2=(41663*22326)^2+(12 566*45567)^2
    3199771405=5*29*41*73*73*101=44749^2+34602^2=56429 ^2+3942^2=49859^2+26718^2=15038^2+54531^2 and (44749*34602)^2+(56429*3942)^2=(49859*26718)^2+(15 038*54531)^2
    6125139445=5*29*41*101*101*101=61913^2+47874^2=780 73^2+5454^2=68983^2+36966^2=20806^2+75447^2 and (61913*47874)^2+(78073*5454)^2=(68983*36966)^2+(20 806*75447)^2
    7133887045=5*29*41*101*109*109=66817^2+51666^2=842 57^2+5886^2=74447^2+39894^2=81423^2+22454^2 and (66817*51666)^2+(84257*5886)^2=(74447*39894)^2+(81 423*22454)^2
    7667082205=5*29*41*101*113*113=69269^2+53562^2=873 49^2+6102^2=77179^2+41358^2=84411^2+23278^2 and (69269*53562)^2+(87349*6102)^2=(77179*41358)^2+(84 411*23278)^2
    13330479445=5*29*41*101*149*149=91337^2+70626^2=11 5177^2+8046^2=101767^2+54534^2=111303^2+30694^2 and (91337*70626)^2+(115177*8046)^2=(101767*54534)^2+( 111303*30694)^2
    14800368805=5*29*41*101*157*157=96241^2+74418^2=12 1361^2+8478^2=107231^2+57462^2=117279^2+32342^2 and (96241*74418)^2+(121361*8478)^2=(107231*57462)^2+( 117279*32342)^2
    47411737645=5*29*41*101*281*281=172253^2+133194^2= 217213^2+15174^2=191923^2+102846^2=209907^2+57886^ 2 and (172253*133194)^2+(217213*15174)^2=(191923*102846) ^2+(209907*57886)^2
    96552156445=5*29*41*101*401*401=245813^2+190074^2= 309973^2+21654^2=273883^2+146766^2=82606^2+299547^ 2 and (245813*190074)^2+(309973*21654)^2=(273883*146766) ^2+(82606*299547)^2
    106423472245=5*29*41*101*421*421=258073^2+199554^2 =325433^2+22734^2=287543^2+154086^2=314487^2+86726 ^2 and (258073*199554)^2+(325433*22734)^2=(287543*154086) ^2+(314487*86726)^2
    440996229805=5*29*41*101*857*857=525341^2+406218^2 =662461^2+46278^2=585331^2+313662^2=176542^2+64017 9^2 and (525341*406218)^2+(662461*46278)^2=(585331*313662) ^2+(176542*640179)^2
    9370351861=13*13*37*37*101*401=14430^2+95719^2=446 94^2+85865^2=26806^2+93015^2=89895^2+35906^2 and (14430*95719)^2+(44694*85865)^2=(26806*93015)^2+(8 9895*35906)^2
    40906198021=13*13*53*73*73*857=193089^2+60190^2=18 3170^2+85761^2=110214^2+169585^2=200239^2+28470^2 and (193089*60190)^2+(183170*85761)^2=(110214*169585)^ 2+(200239*28470)^2
    16023856141=17*17*37*37*101*401=18870^2+125171^2=5 8446^2+112285^2=35054^2+121635^2=117555^2+46954^2 and (18870*125171)^2+(58446*112285)^2=(35054*121635)^2 +(117555*46954)^2
    69952019101=17*17*53*73*73*857=252501^2+78710^2=23 9530^2+112149^2=144126^2+221765^2=261851^2+37230^2 and (252501*78710)^2+(239530*112149)^2=(144126*221765) ^2+(261851*37230)^2
    46629975829=29*29*37*37*101*401=32190^2+213527^2=9 9702^2+191545^2=59798^2+207495^2=200535^2+80098^2 and (32190*213527)^2+(99702*191545)^2=(59798*207495)^2 +(200535*80098)^2
    203562796069=29*29*53*73*73*857=430737^2+134270^2= 408610^2+191313^2=245862^2+378305^2=446687^2+63510 ^2 and (430737*134270)^2+(408610*191313)^2=(245862*378305 )^2+(446687*63510)^2
    75905394661=37*37*37*37*101*401=41070^2+272431^2=1 27206^2+244385^2=76294^2+264735^2=255855^2+102194^ 2 and (41070*272431)^2+(127206*244385)^2=(76294*264735)^ 2+(255855*102194)^2
    93204505789=37*37*41*41*101*401=45510^2+301883^2=1 40958^2+270805^2=283515^2+113242^2=84542^2+293355^ 2 and (45510*301883)^2+(140958*270805)^2=(283515*113242) ^2+(84542*293355)^2
    155747446021=37*37*53*53*101*401=58830^2+390239^2= 182214^2+350065^2=109286^2+379215^2=366495^2+14638 6^2 and (58830*390239)^2+(182214*350065)^2=(109286*379215) ^2+(366495*146386)^2
    331364408821=37*37*53*73*73*857=549561^2+171310^2= 521330^2+244089^2=313686^2+482665^2=569911^2+81030 ^2 and (549561*171310)^2+(521330*244089)^2=(313686*482665 )^2+(569911*81030)^2
    206314078549=37*37*61*61*101*401=67710^2+449143^2= 209718^2+402905^2=421815^2+168482^2=125782^2+43645 5^2 and (67710*449143)^2+(209718*402905)^2=(421815*168482) ^2+(125782*436455)^2
    295471035901=37*37*73*73*101*401=81030^2+537499^2= 250974^2+482165^2=504795^2+201626^2=150526^2+52231 5^2 and (81030*537499)^2+(250974*482165)^2=(504795*201626) ^2+(150526*522315)^2
    565603309669=37*37*101*101*101*401=112110^2+743663 ^2=347238^2+667105^2=208262^2+722655^2=698415^2+27 8962^2 and (112110*743663)^2+(347238*667105)^2=(208262*722655 )^2+(698415*278962)^2
    658752369589=37*37*101*109*109*401=120990^2+802567 ^2=374742^2+719945^2=224758^2+779895^2=753735^2+30 1058^2 and (120990*802567)^2+(374742*719945)^2=(224758*779895 )^2+(753735*301058)^2
    707988301261=37*37*101*113*113*401=125430^2+832019 ^2=388494^2+746365^2=233006^2+808515^2=781395^2+31 2106^2 and (125430*832019)^2+(388494*746365)^2=(233006*808515 )^2+(781395*312106)^2
    1230953737669=37*37*101*149*149*401=165390^2+10970 87^2=512262^2+984145^2=307238^2+1066095^2=1030335^ 2+411538^2 and (165390*1097087)^2+(512262*984145)^2=(307238*10660 95)^2+(1030335*411538)^2
    1366685224981=37*37*101*157*157*401=174270^2+11559 91^2=539766^2+1036985^2=323734^2+1123335^2=1085655 ^2+433634^2 and (174270*1155991)^2+(539766*1036985)^2=(323734*1123 335)^2+(1085655*433634)^2
    4378061262109=37*37*101*281*281*401=311910^2+20690 03^2=966078^2+1856005^2=579422^2+2010555^2=1943115 ^2+776122^2 and (311910*2069003)^2+(966078*1856005)^2=(579422*2010 555)^2+(1943115*776122)^2
    8915751181069=37*37*101*401*401*401=445110^2+29525 63^2=1378638^2+2648605^2=826862^2+2869155^2=277291 5^2+1107562^2 and (445110*2952563)^2+(1378638*2648605)^2=(826862*286 9155)^2+(2772915*1107562)^2
    9827281267429=37*37*101*401*421*421=3099823^2+4673 10^2=2780705^2+1447398^2=3012255^2+868102^2=291121 5^2+1162802^2 and (3099823*467310)^2+(2780705*1447398)^2=(3012255*86 8102)^2+(2911215*1162802)^2
    40722163041181=37*37*101*401*857*857=951270^2+6310 091^2=2946366^2+5660485^2=1767134^2+6131835^2=5926 155^2+2367034^2 and (951270*6310091)^2+(2946366*5660485)^2=(1767134*61 31835)^2+(5926155*2367034)^2
    406883543629=41*41*53*73*73*857=608973^2+189830^2= 577690^2+270477^2=347598^2+534845^2=631523^2+89790 ^2 and (608973*189830)^2+(577690*270477)^2=(347598*534845 )^2+(631523*89790)^2
    679914261781=53*53*53*73*73*857=787209^2+245390^2= 746770^2+349641^2=449334^2+691385^2=816359^2+11607 0^2 and (787209*245390)^2+(746770*349641)^2=(449334*691385 )^2+(816359*116070)^2
    900662501989=53*61*61*73*73*857=939583^2+133590^2= 517158^2+795745^2=859490^2+402417^2=906033^2+28243 0^2 and (939583*133590)^2+(517158*795745)^2=(859490*402417 )^2+(906033*282430)^2
    1289876504461=53*73*73*73*73*857=1084269^2+337990^ 2=1028570^2+481581^2=618894^2+952285^2=1124419^2+1 59870^2 and (1084269*337990)^2+(1028570*481581)^2=(618894*9522 85)^2+(1124419*159870)^2
    2469136840309=53*73*73*101*101*857=1500153^2+46763 0^2=1423090^2+666297^2=856278^2+1317545^2=1555703^ 2+221190^2 and (1500153*467630)^2+(1423090*666297)^2=(856278*1317 545)^2+(1555703*221190)^2
    2875778335429=53*73*73*109*109*857=1618977^2+50467 0^2=1535810^2+719073^2=924102^2+1421905^2=1678927^ 2+238710^2 and (1618977*504670)^2+(1535810*719073)^2=(924102*1421 905)^2+(1678927*238710)^2
    3090717411421=53*73*73*113*113*857=958014^2+147408 5^2=1740539^2+247470^2=1678389^2+523190^2=1592170^ 2+745461^2 and (958014*1474085)^2+(1740539*247470)^2=(1678389*523 190)^2+(1592170*745461)^2
    5373718948309=53*73*73*149*149*857=1263222^2+19437 05^2=2295047^2+326310^2=2213097^2+689870^2=2099410 ^2+982953^2 and (1263222*1943705)^2+(2295047*326310)^2=(2213097*68 9870)^2+(2099410*982953)^2
    5966253698341=53*73*73*157*157*857=1331046^2+20480 65^2=2418271^2+343830^2=2331921^2+726910^2=2212130 ^2+1035729^2 and (1331046*2048065)^2+(2418271*343830)^2=(2331921*72 6910)^2+(2212130*1035729)^2
    19112392319149=53*73*73*281*281*857=4173693^2+1301 030^2=3959290^2+1853757^2=2382318^2+3665645^2=4328 243^2+615390^2 and (4173693*1301030)^2+(3959290*1853757)^2=(2382318*3 665645)^2+(4328243*615390)^2
    38921642295709=53*73*73*401*401*857=5956053^2+1856 630^2=5650090^2+2645397^2=3399678^2+5231045^2=6176 603^2+878190^2 and (5956053*1856630)^2+(5650090*2645397)^2=(3399678*5 231045)^2+(6176603*878190)^2
    42900919783669=53*73*73*421*421*857=3569238^2+5491 945^2=6484663^2+921990^2=6253113^2+1949230^2=59318 90^2+2777337^2 and (3569238*5491945)^2+(6484663*921990)^2=(6253113*19 49230)^2+(5931890*2777337)^2
    177772285386541=53*73*73*857*857*857=12729021^2+39 67910^2=12075130^2+5653629^2=7265646^2+11179565^2= 13200371^2+1876830^2 and (12729021*3967910)^2+(12075130*5653629)^2=(7265646 *11179565)^2+(13200371*1876830)^2
    Last edited by Media_Man; August 30th 2009 at 12:03 PM. Reason: Included the factorizations
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    Some of these look to have common factors. For example the one with hypotenuse 1685125 is just what you get by multiplying the generators of the first solution by 5, and in the last solution you found I think all the terms are divisible by 857.
    It would be worth filtering these out I think, so we can see if you have come up with any genuinely new ones . My program hasn't found any new ones since the one I last posted, even though I set a faster version of it going moving down from the end of my search space. But congratulations if you have found a better way of discovering solutions than by trial search. I was thinking about trying a program that used the strategy of multiplying to k=3 solutions, but haven't got round to it yet.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    My Search Algorithm

    1. Start with a list of 4k+1 primes, including 1. I used {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2  81,401,421,857} simply based on the previous data. A bigger list means more solutions. A smaller list means faster results.

    2. Calculate all possible combinations of 6 factors. (The eight solutions posed so far have 4 and 5, and I wanted more than eight solutions.) By keeping p=1 a prime, I am guaranteed to consider 0,1,2,3,4,5-factor solutions as well.

    3. For each prime, find the corresponding sum of squares. Ex: 5=1^1+2^2, 13=2^2+3^2, 17=1^2+4^2. The literature says such a sum exists, and I'm pretty sure it's unique.

    4. (Complicated to code.) For each number N, use the sums of squares of its prime factors to find sums of squares that equal N. Use the identity: (a^2+b^2)(c^2+d^2)=(ac+bd)^2+(bc-ad)^2=(ad+bc)^2+(bd-ac)^2. Ex: 13*17=(2^2+3^2)(1^2+4^2)=10^2+11^2=5^2+14^2. Given N with k factors, this gives you 2^{k-1} sums of squares, not necessarily unique.

    5. Out of each (m,n) solution to N=m^2+n^2, test every possible combination of four unique ones for our second condition: (m_1n_1)^2+(m_2n_2)^2=(m_3n_3)^2+(m_4n_4)^2. If it passes, it is a solution!

    Some parts of this were difficult to code, but the concept is simple enough. Pro: no factoring, extremely fast and returns lots of solutions. Con: list is NEVER complete, by construction. All values of a_1 are necessarily the product of 6 or fewer primes from the initial list. This kind of defeats the purpose of finding random solutions and extracting a pattern. Instead, I am taking a pattern and finding all solutions that exhibit that same pattern.

    Attached is the text to the java app I made. There are three possible solutions that this algorithm cannot get: 1) a_1 values with more than six prime factors. 2) a_1 values with prime factors of the form 4k+3, but to an even power, so that it is still expressible as the sums of squares. 3) a_1 values with prime factors not included in the initial list. There are things we can do to get around these limits, but with a great sacrifice of speed.

    I think it's time we shift our attention away from the computing aspect of the problem and go back to the theory: Is there a formula producing these a_1 values for which our conditions necessarily hold?
    Attached Files Attached Files
    Last edited by Media_Man; August 30th 2009 at 11:55 AM. Reason: misspelling
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by alunw View Post
    Some of these look to have common factors. For example the one with hypotenuse 1685125 is just what you get by multiplying the generators of the first solution by 5, and in the last solution you found I think all the terms are divisible by 857.
    It would be worth filtering these out I think, so we can see if you have come up with any genuinely new ones . My program hasn't found any new ones since the one I last posted, even though I set a faster version of it going moving down from the end of my search space. But congratulations if you have found a better way of discovering solutions than by trial search. I was thinking about trying a program that used the strategy of multiplying to k=3 solutions, but haven't got round to it yet.
    Generally speaking, if two hypotenuses a_1 and a_{11} are such that a_{11} = q^2a_1 then they belong to the same family. This is the case with 67405 and 1685125 since 1685125 = (5^2)(67405)
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    I think it's time we shift our attention away from the computing aspect of the problem and go back to the theory: Is there a formula producing these a_1 values for which our conditions necessarily hold?
    Your conditon 5) is new to me I think. It may make things easier.

    I'm currently working off of my mini Ubuntu so the algorithms you guys have will run slow on my laptop.

    I suspect the kind of formula your thinking of is currently unknown. For the k = 4 case, I assume that for given inputs (a,b,c,d,e,f,g,h), your looking for some kind of formula f_n(a,b,c,d,e,f,g,h) that outputs the nth k = 4 member, yes?
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    A Magic Formula

    Quote Originally Posted by jamix View Post
    I suspect the kind of formula your thinking of is currently unknown. For the k = 4 case, I assume that for given inputs (a,b,c,d,e,f,g,h), your looking for some kind of formula f_n(a,b,c,d,e,f,g,h) that outputs the nth k = 4 member, yes?
    That is correct. If we could find a function A_n(a,b,c,d,e,f,g,h) for the nth k=4 member, then deriving B_n(a,b,c,d,e,f,g,h), C_n(a,b,c,d,e,f,g,h), E_n(a,b,c,d,e,f,g,h) should be straightforward. To get a k=5 member, all we need is two k=4 members such that A_i=A_j, B_i=B_j, C_i=C_j (multiplying them together guarantees a k=5 member). If we have a formula I am sure we could a) find two k=4 members satisfying these criteria or b) prove none exists.

    There is certainly no known formula, otherwise Pomerance would have long since done this.
    Follow Math Help Forum on Facebook and Google+

  8. #23
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    Quote Originally Posted by Media_Man View Post
    1. Start with a list of 4k+1 primes, including 1. I used [tex]
    3. For each prime, find the corresponding sum of squares. Ex: 5=1^1+2^2, 13=2^2+3^2, 17=1^2+4^2. The literature says such a sum exists, and I'm pretty sure it's unique.
    I thought it was known that this was unique, and even that this could be used as a primality test for numbers of this form, but I'm not so sure now as I can't find a reference for this.
    Follow Math Help Forum on Facebook and Google+

  9. #24
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Raw Data

    Alunw - I am pretty sure you are correct, though I could not find reference to this fact either. In our specific problem, it makes no difference.

    Attached is the updated *.xls file. (Sorry, non-Office users - blame the site, not me.)

    At last here is our generating algorithm in simplest form:

    a^2+b^2=c^2+d^2=e^2+f^2=g^2+h^2=A
    2(a^2b^2+c^2d^2)=2(e^2f^2+g^2h^2)=B
    2|a^2b^2-c^2d^2|=C_1
    2|e^2f^2-g^2h^2|=C_2
    (These are the C-values for the two k=3 ladders that multiply to get the desired k=4 ladder)
    \frac12(C_1^2+C_2^2)=C
    \frac12|C_1^2-C_2^2|=D

    The eight roots can be gotten by r=a\pm b, c\pm d, e\pm f, g\pm h or by r^2=A\pm\sqrt{B\pm\sqrt{C\pm D}}
    Attached Files Attached Files
    Last edited by Media_Man; August 30th 2009 at 02:34 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  10. #25
    Member
    Joined
    Jun 2008
    Posts
    148
    I haven't been able to download your last few attachments. I guess its fine (just means I won't be able to add any corrections or whatnot).

    Your generating algorithm isn't what I thought you originally had in mind. These conditions can actually be found in a 1999 paper by Dilcher (surprisingly Dilcher's paper is flawed since he claims to have proved that no such integer set (a,b,,c,d,e,f,g,h) can satisfy these conditions ).

    To be clear, I don't actually know whether or not there are any k = 5 ladders that have been discovered. I doubt that there has been though. Pomerance probably wouldn't know for sure either. This problem was actually brought up by his coauthor Richard Crandall.
    Follow Math Help Forum on Facebook and Google+

  11. #26
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Pomerance's Text

    Jamix - This is from pg 316 in the Crandall/Pomerance textbook:

    Theoretical work on such issues does exist; for example, [Dilcher 1999]
    discourses on the difficulty of creating longer squaring ladders of the indicated
    kind. Recently, D. Symes has discovered a (k = 4) identity, with coefficients
    (a1, a2, a3, a4) as implied in the construct
    (((x^2-67405)^2-3525798096)^2-533470702551552000)^2-4692082091913216002
    which, as the reader may wish to verify via symbolic processing, is indeed
    the product of 16 monomials! P. Carmody recently reports that many such
    4-squarings cases are easy to generate via, say, a GP/Pari script.
    Notice that Symes has found our smallest example. So we are pretty far ahead of the curve. I'd be interested in seeing Carmody's results. It says here that Dilcher said the problem was difficult, not impossible. Can you post his paper with the purported faulty proof?

    P.S. A few months back when we were working on Carmichael numbers, I was a bit discouraged to have rediscovered something that appeared in a 1910 paper! I feel better now having produced results that are at least as recent as 2005
    Last edited by Media_Man; August 30th 2009 at 05:09 PM. Reason: the voices told me to
    Follow Math Help Forum on Facebook and Google+

  12. #27
    Member
    Joined
    Jun 2008
    Posts
    148
    Can you PM me your email address and I'll try sending it to you through my gmail account. I actually tried attaching it a few days ago in the other thread but it wouldn't upload for some reason.

    I haven't looked if Carmody has ever published any of his results. Sometimes these guys just like to communicate or muse between each other on what they've got (kinda like we often do on this forum). As k = 4 ladders are still too small to be of any real use as a factoring algorithm, some authors might not publish new ones. On the other hand, you can always try and start a trend. After all, there are all kinds of lists of certain mathematical things or integers that have been documented. For example, Richard Pinch appears to have made it his goal to document every single Carmichael integer he can find.
    Follow Math Help Forum on Facebook and Google+

  13. #28
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Repeats

    Good call on the common factors. Turns out, a lot of my solutions were repeats. . My eighty solutions actually only contain eight "primitive" solutions:


    67405=1*1*5*13*17*61=227^2+126^2=218^2+141^2=189^2 +178^2=237^2+106^2 and (227*126)^2+(218*141)^2=(189*178)^2+(237*106)^2
    600445=1*1*5*29*41*101=613^2+474^2=773^2+54^2=683^ 2+366^2=206^2+747^2 and (613*474)^2+(773*54)^2=(683*366)^2+(206*747)^2
    55445869=1*1*37*37*101*401=1110^2+7363^2=3438^2+66 05^2=2062^2+7155^2=6915^2+2762^2 and (1110*7363)^2+(3438*6605)^2=(2062*7155)^2+(6915*27 62)^2
    242048509=1*1*53*73*73*857=14853^2+4630^2=14090^2+ 6597^2=8478^2+13045^2=15403^2+2190^2 and (14853*4630)^2+(14090*6597)^2=(8478*13045)^2+(1540 3*2190)^2
    5915065=1*5*13*17*53*101=2076^2+1267^2=2428^2+141^ 2=2324^2+717^2=2253^2+916^2 and (2076*1267)^2+(2428*141)^2=(2324*717)^2+(2253*916) ^2
    81524605=1*5*17*41*149*157=8498^2+3051^2=8629^2+26 58^2=7947^2+4286^2=9003^2+686^2 and (8498*3051)^2+(8629*2658)^2=(7947*4286)^2+(9003*68 6)^2
    532946005=1*5*17*53*281*421=19598^2+12201^2=20583^ 2+10454^2=21366^2+8743^2=17769^2+14738^2 and (19598*12201)^2+(20583*10454)^2=(21366*8743)^2+(17 769*14738)^2
    166045477=1*13*17*61*109*113=12606^2+2671^2=10609^ 2+7314^2=12351^2+3674^2=11199^2+6374^2 and (12606*2671)^2+(10609*7314)^2=(12351*3674)^2+(1119 9*6374)^2

    Looking at the algebra, it is clear that you can multiply any value of A by a square to get a new solution x^2A=(xa)^2+(xb)^2..., like jamix said all along.

    Something odd/useful though: Using the same exact algorithm to look for solutions for A up to six factors, these are the only solutions I found, the same eight five-factor ones that you guys found before I made my own algorithm. This means that no combination of six prime factors from the list {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857} make a solution. All the six-factor solutions I thought I'd found earlier were simply four-factor primitives with an extra x^2 factor. I doubt this means no six-factor primitive solutions exist, but I am now intrigued. I'm going to try to run my algorithm with all primes up to 1000, instead of just this small set. Maybe it will terminate in a few *days* and give me what I'm looking for, a six-factor primitive solution.
    Follow Math Help Forum on Facebook and Google+

  14. #29
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408
    AHA!

    12781559905=5*17*29*37*353*397=101256^2+50287^2=39 753^2+105836^2=111992^2+15471^2=76983^2+82796^2 and (101256*50287)^2+(39753*105836)^2=(111992*15471)^2 +(76983*82796)^2

    Program still running, but I needed to vindicate myself after that false alarm I pulled.
    Follow Math Help Forum on Facebook and Google+

  15. #30
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Polar fun

    Since I'm on a polar binge, I figured a way to run the algorithm a bit smoother using trig. Consider the identity (a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(bc\mp ad)^2. In polar, this is actually r_1r_2=\left(\sqrt{r_1r_2}\cos(\theta_1\pm\theta_2  )\right)^2+\left(\sqrt{r_1r_2}\sin(\theta_1\pm\the  ta_2)\right)^2

    Example: Let r_1=13=2^2+3^2 and r_2=17=1^2+4^2. Then \theta_1\approx .9827 and \theta_2\approx 1.3258. And voila...

    \sqrt{221}\cos(.9827+1.3258)=-10
    \sqrt{221}\sin(.9827+1.3258)=11
    \sqrt{221}\cos(.9827-1.3258)=14
    \sqrt{221}\sin(.9827-1.3258)=-5

    So 10^2+11^2=14^2+5^2=221. So given the factors of a large number N, I can extremely quickly find all integer solutions x,y to N=x^2+y^2. For our purposes, we'll need to use a polynomial to approximate sine and cosine for speed, though. This will be much faster than the loop structure and function calls I have in place now.

    (After three days, my program is still running, though not turning up anything new . I am trying to pare it down as much as possible for another run.)
    Follow Math Help Forum on Facebook and Google+

Page 2 of 3 FirstFirst 123 LastLast

Similar Math Help Forum Discussions

  1. Integer solutions to a^2+b^2=c^3
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2014, 08:22 AM
  2. No integer Solutions
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 16th 2011, 03:01 AM
  3. integer solutions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 28th 2011, 09:07 AM
  4. Replies: 2
    Last Post: May 8th 2010, 10:59 PM
  5. Integer Solutions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 31st 2009, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum