1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #!/usr/bin/ruby
- # T(10^3) = 474 and T(10^6) = 492128.
- # The numbers n seem to be the squares and also numbers of the form:
- # p * k^2, where p is a prime >= 41
- # https://projecteuler.net/problem=804
- var total = 0
- #var N = 1548
- var N = 1e3
- var S = N.isqrt
- var table = Hash()
- var a = 41
- for n in (1..N), b in (0..S) {
- var c = (b*b - n)
- var D = (b*b - 4*a*c)
- if (D.is_square) {
- total += 1
- table{n} := 0 ++
- }
- }
- say 2*total
- #say [table{table.keys.map{.to_i}.grep{.is_prime}...}].sort
- #say [table{table.keys.map{.to_i}.grep{!.is_square}...}].sort
- #say table.grep{|k,v| k.to_i.is_prime }.keys.map{.to_i}.sort
- #say table.grep{|k,v| k.to_i.is_square }
- #say table.grep{|k,v| k.to_i.is_composite && !k.to_i.is_square && (k.to_i/4 -> is_composite) }
- say table.keys.map{.to_i}.sort
- __END__
- # Values of n:
- [1, 4, 9, 16, 25, 36, 41, 43, 47, 49, 53, 61, 64, 71, 81, 83, 97, 100, 113, 121, 131, 144, 151, 163, 164, 167, 169, 172, 173, 179, 188, 196, 197, 199, 212, 223, 225, 227, 244, 251, 256, 263, 281, 284, 289, 307, 313, 324, 332, 347, 359, 361, 367, 369, 373, 379, 383, 387, 388, 397, 400, 409, 419, 421, 423, 439, 441, 452, 457, 461, 477, 484, 487, 499, 503, 523, 524, 529, 547, 549, 563, 576, 577, 593, 604, 607, 625, 639, 641, 647, 652, 653, 656, 661, 668, 673, 676, 677, 688, 691, 692, 701, 709, 716, 729, 733, 739, 743, 747, 752, 773, 784, 787, 788, 796, 797, 821, 829, 839, 841, 848, 853, 873, 877, 892, 900, 908, 911, 919, 941, 947, 961, 967, 971, 976, 1004, 1013, 1017, 1019, 1021, 1024, 1025, 1031, 1033, 1039, 1049, 1052, 1061, 1063, 1069, 1075, 1089, 1091, 1093, 1097, 1109, 1123, 1124, 1129, 1136, 1151, 1156, 1163, 1175, 1179, 1181, 1187, 1201, 1225, 1228, 1229, 1231, 1237, 1252, 1259, 1277, 1291, 1296, 1297, 1301, 1319, 1325, 1328, 1359, 1361, 1369, 1373, 1381, 1388, 1399, 1423, 1436, 1439, 1444, 1447, 1459, 1467, 1468, 1471, 1476, 1481, 1483, 1489, 1492, 1493, 1503, 1516, 1521, 1523, 1525, 1531, 1532, 1548]
- # Non-squares:
- [41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 163, 164, 167, 172, 173, 179, 188, 197, 199, 212, 223, 227, 244, 251, 263, 281, 284, 307, 313, 332, 347, 359, 367, 369, 373, 379, 383, 387, 388, 397, 409, 419, 421, 423, 439, 452, 457, 461, 477, 487, 499, 503, 523, 524, 547, 549, 563, 577, 593, 604, 607, 639, 641, 647, 652, 653, 656, 661, 668, 673, 677, 688, 691, 692, 701, 709, 716, 733, 739, 743, 747, 752, 773, 787, 788, 796, 797, 821, 829, 839, 848, 853, 873, 877, 892, 908, 911, 919, 941, 947, 967, 971, 976, 1004, 1013, 1017, 1019, 1021, 1025, 1031, 1033, 1039, 1049, 1052, 1061, 1063, 1069, 1075, 1091, 1093, 1097, 1109, 1123, 1124, 1129, 1136, 1151, 1163, 1175, 1179, 1181, 1187, 1201, 1228, 1229, 1231, 1237, 1252, 1259, 1277, 1291, 1297, 1301, 1319, 1325, 1328, 1359, 1361, 1373, 1381, 1388, 1399, 1423, 1436, 1439, 1447, 1459, 1467, 1468, 1471, 1476, 1481, 1483, 1489, 1492, 1493, 1503, 1516, 1523, 1525, 1531, 1532, 1548]
- # Primes:
- [41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 163, 167, 173, 179, 197, 199, 223, 227, 251, 263, 281, 307, 313, 347, 359, 367, 373, 379, 383, 397, 409, 419, 421, 439, 457, 461, 487, 499, 503, 523, 547, 563, 577, 593, 607, 641, 647, 653, 661, 673, 677, 691, 701, 709, 733, 739, 743, 773, 787, 797, 821, 829, 839, 853, 877, 911, 919, 941, 947, 967, 971, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1061, 1063, 1069, 1091, 1093, 1097, 1109, 1123, 1129, 1151, 1163, 1181, 1187, 1201, 1229, 1231, 1237, 1259, 1277, 1291, 1297, 1301, 1319, 1361, 1373, 1381, 1399, 1423, 1439, 1447, 1459, 1471, 1481, 1483, 1489, 1493, 1523, 1531]
- # Non-squares and non-primes:
- [164, 172, 188, 212, 244, 284, 332, 369, 387, 388, 423, 452, 477, 524, 549, 604, 639, 652, 656, 668, 688, 692, 716, 747, 752, 788, 796, 848, 873, 892, 908, 976, 1004, 1017, 1025, 1052, 1075, 1124, 1136, 1175, 1179, 1228, 1252, 1325, 1328, 1359, 1388, 1436, 1467, 1468, 1476, 1492, 1503, 1516, 1525, 1532, 1548]
|