Let a fun number be a positive integer of the form 4x+1. Then, the fun numbers are 1, 5, 9, 13, 17, 21, 25, 29, 33, 37... Let a fun prime be a fun number that is not divisible by any fun number other than 1 and itself. For example, 5 is a fun prime. Also, even though 9=3*3, 9 is a fun prime because 3 is not a fun number. Now, every fun number can be factored into fun primes. For example, 25=5*5. Find the first fun number with more than one fun prime factorization.
The first fun number with more than one fun prime factorization is 441, which is 9*49 or 21^2.
The program at the bottom lists the fun primes beyond 5, stopping after 500 fun primes have been found, but intersperses this with lines beginning with * which show fun numbers that meet the criterion of having more than one fun prime factorization. The fun prime divisors of the number are shown as is their product. The product's being larger than the number itself shows there is more than one factorization. In the case there are two factorizations, that product is usually the square of the found number (see 2205 for a number where the two factorizations share one factor).
The first version of the program did not consider multiple occurrences of the same prime factor, as in 21^2, but came out with the same resulting number identifications. I'm assuming that with higher numbers there might be occasions where counting only 1 of more than one occurrence might prevent the product from exceeding the number, in which case such a situation would go undetected; thus the inclusion of separately counting a factor as many times as it occurred.
Also, I'm not sure if the preliminary check that more than one prime factor below the square root actually sped the processing time for such small numbers as tested here. It's a remnant of a failed method, as such a situation is necessary but not sufficient to indicate the multiple factorizations sought, as a number could be just the product of several small primes, rather than a small prime times a large prime.
9 13 17 21 29 33 37 41 49 53 57 61 69 73 77 89 93 97 101 109 113 121 129 133 137 141 149 157 161 173 177 181 193 197 201 209 213 217 229 233 237 241 249 253 257 269 277 281 293 301 309 313 317 321 329 337 341 349 353 361 373 381 389 393 397 401 409 413 417 421 433 437
* 441 9 21 21 49 194481
449 453 457 461 469 473 489 497 501 509 517 521 529 537 541 553 557 569 573 577 581 589 593 597 601 613 617 633 641 649 653 661 669 673 677 681
* 693 9 21 33 77 480249
701 709 713 717 721 733 737 749 753 757 761 769 773 781 789 797 809 813 817 821 829 849 853 857 869 877 881 889 893 913 917 921 929 933 937 941 953 961 973 977 989 993 997 1009 1013 1021 1033 1041 1049 1057 1061 1069 1077 1081
* 1089 9 33 33 121 1185921
1093 1097 1101 1109 1117 1121 1129 1133 1137 1141 1149 1153 1169 1177 1181 1193
* 1197 9 21 57 133 1432809
1201 1213 1217 1229 1237 1249 1253 1257 1273 1277 1289 1293 1297 1301 1317 1321 1329 1333 1337 1349 1357 1361 1373 1381 1389 1393 1397 1401 1409 1429 1433 1437 1441
* 1449 9 21 69 161 2099601
1453 1457 1461 1473 1477 1481 1489 1493 1497 1501 1509 1529 1541 1549 1553 1561 1569 1577 1589 1597 1601 1609 1613
* 1617 21 33 49 77 2614689
1621 1633 1637 1641 1657 1661 1669 1673 1689 1693 1697 1709 1713 1721 1733 1741 1753 1757 1761 1777 1789 1793 1797 1801 1817 1821 1829 1837 1841 1849 1857 1861 1873 1877
* 1881 9 33 57 209 3538161
1889 1893 1897 1901 1909 1913 1929 1933 1941 1949
* 1953 9 21 93 217 3814209
1957 1969 1973 1977 1981 1993 1997 2017 2021 2029 2033 2049 2053 2069 2073 2077 2081 2089 2101 2113 2129 2137 2141 2149 2153 2157 2161 2177 2181 2189 2201
* 2205 5 9 21 21 49 972405
2209 2213 2217 2221 2229 2237 2253 2269 2273
* 2277 9 33 69 253 5184729
2281 2293 2297 2309 2317 2321 2333 2341 2357 2361 2369 2377 2381 2389 2393 2413 2417 2429 2433 2437 2441 2449 2453 2461 2469 2473 2477 2481 2489 2497 2513 2517 2521 2537
* 2541 21 33 77 121 6456681
2549 2557 2569 2573 2577 2589 2593 2609 2617 2621 2629 2633 2641 2649 2653 2657 2661 2677 2681 2689 2693
* 2709 9 21 129 301 7338681
2713 2721 2729 2733 2741 2749 2753 2757 2761 2773 2777 2789
* 2793 21 49 57 133 7800849
2797 2801 2833 2837 2841 2857 2861 2869 2881 2893 2897 2901 2909 2913 2917 2921 2933 2949 2953 2957
* 2961 9 21 141 329 8767521
2969 2973 2981 3001 3013 3017 3037 3041 3049 3053 3057 3061
* 3069 9 33 93 341 9418761
3073 3089 3093 3097 3101 3109 3113 3117 3121 3137 3149 3153 3169 3173 3181 3189 3193 3197 3209 3217 3221 3229 3241
* 3249 9 57 57 361 10556001
3253 3257 3261 3269 3273 3301 3309 3313 3317 3329 3337 3353 3361 3369 3373 3377
* 3381 21 49 69 161 11431161
3389 3397 3401 3409 3413 3421 3433 3437 3449 3453 3457 3461
* 3465 5 9 21 33 77 2401245
3469 3473 3481 3489 3493 3513 3517 3521 3529 3533 3541 3557 3561 3569 3581 3593 3613 3617 3629 3637 3641 3661 3669 3673 3677 3693 3697 3701 3709 3713
* 3717 9 21 177 413 13816089
3733 3749
DefDbl A-Z
Dim crlf$, fp(1000), dr(50)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
fp(1) = 5: fpCt = 1
For n = 5 To 100001 Step 4
lim = Sqr(n)
pptr = 1: dvsbl = 0: dvCt = 0
Do
q = Int(n / fp(pptr)): r = n - fp(pptr) * q
If r = 0 Then
dvsbl = 1: dvCt = dvCt + 1
dr(dvCt) = fp(pptr)
End If
DoEvents
pptr = pptr + 1
Loop Until fp(pptr) > lim Or pptr > fpCt
If dvsbl = 0 Then
fpCt = fpCt + 1
fp(fpCt) = n
Text1.Text = Text1.Text & Str(n)
Else
If dvCt > 1 Then
pptr = 1: dvsbl = 0: dvCt = 0: prodDiv = 1
Do
n2 = n
Do
q = Int(n2 / fp(pptr)): r = n2 - fp(pptr) * q
If r = 0 Then
dvsbl = 1: dvCt = dvCt + 1
dr(dvCt) = fp(pptr)
prodDiv = prodDiv * dr(dvCt)
n2 = n2 / dr(dvCt)
End If
DoEvents
Loop Until r > 0
pptr = pptr + 1
Loop Until pptr > fpCt
If prodDiv > n Then
Text1.Text = Text1.Text & crlf & "* " & n & " "
For i = 1 To dvCt
Text1.Text = Text1.Text & Str(dr(i))
Next
Text1.Text = Text1.Text & " " & prodDiv & crlf
End If
End If
End If
If fpCt > 500 Then Exit For
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Edited on November 14, 2017, 2:11 pm
|
|
Posted by Charlie
on 2017-11-14 14:08:09 |
computer solution
