/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/3qyb
*/
package {
import flash.display.Sprite;
import flash.events.Event;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=272
public class Euler272 extends Sprite {
private var _tf : TextField;
public function Euler272() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
tr(solve());
var g : int = getTimer();
tr((g - s) + " ms");
}
private var _pmap : Object;
private function solve() : void
{
var N : Number = Math.pow(10, 7.5);
var primes : Array = doEratosthenes(N / 7 / 9 / 13 / 19);
_pmap = {};
var p : uint;
for each(p in primes){
_pmap[p] = 1;
}
tr(primes.length);
var i : uint, j : uint, k : uint;
var tris : Array = [3];
for(i = 2;i < primes.length;i++){
p = primes[i];
var a : uint = ((p + 1) * (p + 1) / 4 - 1) % p;
if(calcLegendreCore(a, p) == 1){
tris.push(p);
}
}
tr(tris.length);
tr(tris.slice(0, 20));
var nb : uint = N / 7 / 9 / 13 / 19 / 31;
var oks : Array = new Array(nb + 1);
for(i = 0;i <= nb;i++){
oks[i] = i;
}
for each(var tri : uint in tris){
if(tri == 3)tri = 9;
for(i = tri;i <= nb;i += tri){
oks[i] = 0;
}
}
for(i = 1;i <= nb;i++){
oks[i] += oks[i-1];
}
tr(oks.slice(0, 20));
tr(nb);
var su : Number = 0;
var sl : Number = 0;
var ct : uint = 0;
// for(var i1 : uint = 0;i1 < tris.length - 4;i1++){
// var u1 : Number = N / (tris[i1+1] * tris[i1+2] * tris[i1+3] * tris[i1+4]);
// if(u1 < tris[i1])break;
var i1 : uint = 0;
addEventListener(Event.ENTER_FRAME, function(e : Event) : void {
var u1 : Number = N / (tris[i1+1] * tris[i1+2] * tris[i1+3] * tris[i1+4]);
for(var j1 : Number = i1 == 0 ? 9 : tris[i1];j1 <= u1;j1*=tris[i1]){
for(var i2 : uint = i1+1;i2 < tris.length - 3;i2++){
var u2 : Number = N / (j1 * tris[i2+1] * tris[i2+2] * tris[i2+3]);
if(u2 < tris[i2])break;
for(var j2 : Number = tris[i2];j2 <= u2;j2*=tris[i2]){
for(var i3 : uint = i2+1;i3 < tris.length - 2;i3++){
var u3 : Number = N / (j1 * j2 * tris[i3+1] * tris[i3+2]);
if(u3 < tris[i3])break;
for(var j3 : Number = tris[i3];j3 <= u3;j3*=tris[i3]){
for(var i4 : uint = i3+1;i4 < tris.length - 1;i4++){
var u4 : Number = N / (j1 * j2 * j3 * tris[i4+1]);
if(u4 < tris[i4])break;
for(var j4 : Number = tris[i4];j4 <= u4;j4*=tris[i4]){
for(var i5 : uint = i4+1;i5 < tris.length;i5++){
var u5 : Number = N / (j1 * j2 * j3 * j4);
if(u5 < tris[i5])break;
for(var j5 : Number = tris[i5];j5 <= u5;j5*=tris[i5]){
var upper : uint = N / (j1*j2*j3*j4*j5);
tr(j1, j2, j3, j4, j5, oks[upper], oks[upper]*j1*j2*j3*j4*j5);
// var plusM : MPI = MPI.mul(new MPI(oks[upper]), new MPI(j1*j2*j3*j4*j5));
// tr(plusM, oks[upper]*j1*j2*j3*j4*j5, oks[upper], j1*j2*j3*j4*j5);
// removeEventListener(Event.ENTER_FRAME, arguments.callee);
// return;
// sx.add_(plusM);
// }else{
var plus : Number = oks[upper]*j1*j2*j3*j4*j5;
su += Math.floor(plus / 1000000);
sl += plus % 1000000;
// }
ct++;
}}}}}}}}}
if(u1 < tris[i1]){
removeEventListener(Event.ENTER_FRAME, arguments.callee);
// tr(MPI.mul(new MPI(su), new MPI(1000000)).add_(new MPI(sl)).add_(sx));
tr(MPI.mul(new MPI(su), new MPI(1000000)).add_(new MPI(sl)));
return;
}
i1++;
tr(i1, su, sl, ct);
});
}
private function doEratosthenes(n : int) : Array
{
var nn : uint = ((n / 2 - 1) >>> 5) + 1;
var ar : Vector.<uint> = new Vector.<uint>(nn);
var i : uint, j : uint;
for(i = 0;i < nn - 1;i++)ar[i] = 0xffffffff;
ar[nn - 1] = (1 << ((n / 2 - 1) & 31)) - 1;
var sq : uint = (Math.sqrt(n) - 3) >>> 1;
for(var p : uint = 0;p <= sq;p++){
if(ar[p >>> 5] & (1 << (p & 31))){
var m : uint = (p << 1) + 3;
var m2 : uint = m << 1;
for(var mm : uint = m * m;mm <= n;mm += m2){
var ind : uint = (mm - 3) >>> 1;
ar[ind >>> 5] &= ~(1 << (ind & 31));
}
}
}
var ret : Array = [2];
for(i = 0;i < nn;i++){
for(j = 0;j <= 31;j++){
if(ar[i] & (1 << j))ret.push((((i << 5) | j) << 1) + 3);
}
}
return ret;
}
// (a,b)=1, b:odd prime
private function calcLegendreCore(a : uint, b : uint) : int
{
// tr(a, b);
if(a == 1){
return 1;
}
// Jacobi symbol
if(a == 2){
return (b % 8 == 1 || b % 8 == 7) ? 1 : -1;
}
if(a == b - 1){
return b % 4 == 1 ? 1 : -1;
}
var ret : int = 1;
if(a < b){
// Quadratic Reciprocity
if(a % 2 == 1 && b % 2 == 1 && isPrime(a) && isPrime(b)){
var c : uint = a; a = b; b = c;
if(a % 4 == 3 && b % 4 == 3){
ret = -ret;
}
}
}
a %= b;
for(var i : uint = 2;i * i <= a;i++){
for(var ct : uint = 0;a % i == 0;ct++){
a /= i;
}
if(ct % 2 == 1){
ret *= calcLegendreCore(i, b);
}
}
if(a != 1)ret *= calcLegendreCore(a, b);
return ret;
}
// private var _cache : Object = {};
private function isPrime(n : Number) : Boolean
{
return _pmap[n];
/*
if(n <= 1)return false;
if(n % 2 == 0)return n == 2;
if(_cache[n])return _cache[n];
var sq : int = Math.sqrt(n);
for(var i : int = 3;i <= sq;i+=2){
if(n % i == 0){
_cache[n] = false;
return false;
}
}
_cache[n] = true;
return true;
*/
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
class MPI
{
public var d : Vector.<uint>;
public function MPI(v : * = 0)
{
if(v is Number){
d = Vector.<uint>([]);
for(var n : Number = v;n != 0;n = Math.floor(n / 10))d.push(n % 10);
if(v == 0)d.push(0);
}else if(v is String){
d = Vector.<uint>([]);
for(var i : int = v.length - 1;i >= 0;i--){
d.push(uint(v.charAt(i)));
}
}else if(v is Array){
d = Vector.<uint>(v);
}else if(v is Vector.<uint>){
d = v.concat();
}else if(v is MPI){
d = v.d.concat();
}
if(d)shave();
}
public static function add(a : MPI, b : MPI) : MPI
{
if(b == null)return a;
var ret : MPI = new MPI(a);
var i : uint;
var minl : uint = Math.min(ret.d.length, b.d.length);
for(i = 0;i < minl;i++){
ret.d[i] += b.d[i];
}
for(i = ret.d.length;i < b.d.length;i++){
ret.d.push(b.d[i]);
}
ret.carry();
return ret;
}
public function add_(b : MPI) : MPI
{
if(b == null)return this;
var i : uint;
var minl : uint = Math.min(this.d.length, b.d.length);
for(i = 0;i < minl;i++){
this.d[i] += b.d[i];
}
for(i = this.d.length;i < b.d.length;i++){
this.d.push(b.d[i]);
}
this.carry();
return this;
}
public static function addint(a : MPI, b : int) : MPI
{
var ret : MPI = new MPI(a);
ret.d[0] += b;
ret.carry();
return ret;
}
public function addint_(b : int) : MPI
{
this.d[0] += b;
this.carry();
return this;
}
public function inc() : void
{
d[0]++;
for(var i : uint = 0;i < d.length;i++){
if(d[i] >= 10){
var c : uint = d[i] / 10;
if(i == d.length - 1){
d.push(0);
}
d[i + 1] += c;
d[i] %= 10;
}else{
break;
}
}
}
public static function sub(a: MPI, b : MPI) : MPI
{
if(b == null)return a;
if(comp(a, b) < 0){
var m : MPI = a; a = b; b = m;
}
// a - b
var ret : MPI = new MPI(a);
var i : uint;
for(i = 0;i < b.d.length;i++){
ret.d[i] -= b.d[i];
}
ret.minuscarry();
return ret;
}
public function sub_(b : MPI) : MPI
{
if(b == null)return this;
// a - b
var i : uint;
for(i = 0;i < b.d.length;i++){
this.d[i] -= b.d[i];
}
this.minuscarry();
return this;
}
public static function subint(a : MPI, b : int) : MPI
{
var ret : MPI = new MPI(a);
ret.d[0] -= b;
ret.minuscarry();
return ret;
}
public function subint_(b : int) : MPI
{
this.d[0] -= b;
this.minuscarry();
return this;
}
public static function comp(a : MPI, b : MPI) : int
{
if(a.d.length != b.d.length)return a.d.length - b.d.length;
for(var i : int = a.d.length - 1;i >= 0;i--){
if(a.d[i] != b.d[i]){
return a.d[i] - b.d[i];
}
}
return 0;
}
public static function mul(a : MPI, b : MPI) : MPI
{
var retv : Vector.<uint> = new Vector.<uint>(a.d.length + b.d.length);
var i : uint, j : uint;
for(i = 0;i < retv.length;i++)retv[i] = 0;
for(i = 0;i < a.d.length;i++){
for(j = 0;j < b.d.length;j++){
retv[i + j] += a.d[i] * b.d[j];
}
}
var ret : MPI = new MPI(retv);
ret.carry();
ret.shave();
return ret;
}
public static function mulint(a : MPI, b : int) : MPI
{
var ret : MPI = new MPI(a);
for(var i : uint = 0;i < ret.d.length;i++){
ret.d[i] *= b;
}
ret.carry();
return ret;
}
public function mulint_(b : int) : MPI
{
for(var i : uint = 0;i < d.length;i++){
this.d[i] *= b;
}
this.carry();
return this;
}
public static function div(a : MPI, b : MPI) : Array
{
var bm : Array = new Array(10);
var i : int, j : uint;
for(i = 1;i <= 9;i++)bm[i] = mulint(b, i);
var retr : Vector.<uint> = Vector.<uint>([]);
var m : MPI = new MPI(0);
for(i = a.d.length - 1;i >= 0;i--){
m.mul10(1);
m = addint(m, a.d[i]);
for(j = 1;j <= 9;j++){
if(comp(m, bm[j]) < 0)break;
}
retr.push(j - 1);
if(j >= 2)m.sub_(bm[j - 1]);
}
var ret : MPI = new MPI(retr.reverse());
ret.shave();
m.shave();
return [ret, m];
}
public static function divint(a : MPI, b : int) : Array
{
var i : int;
var retr : Vector.<uint> = Vector.<uint>([]);
var m : int = 0;
for(i = a.d.length - 1;i >= 0;i--){
m = m * 10 + a.d[i];
var dv : int = m / b;
retr.push(dv);
m %= b;
}
var ret : MPI = new MPI(retr.reverse());
ret.shave();
return [ret, m];
}
// 末尾の0の個数
public function nLast0() : int
{
for(var i : uint = 0;i < d.length && d[i] == 0;i++);
return i;
}
// 位上げ
public function carry() : void
{
for(var i : uint = 0;i < d.length;i++){
if(d[i] >= 10){
var c : uint = d[i] / 10;
if(i == d.length - 1){
d.push(0);
}
d[i + 1] += c;
d[i] %= 10;
}
}
}
// 位下げ
public function minuscarry() : void
{
for(var i : uint = 0;i < d.length;i++){
if(d[i] <= 2147483648)continue; // やっつけ
var v : int = d[i] - 4294967296;
var c : int = (-v + 9) / 10;
d[i + 1] -= c;
d[i] += 10 * c;
}
shave();
}
// 上位の桁から0を削る
public function shave() : void
{
for(var i : uint = d.length - 1;i >= 1;i--){
if(d[i] > 0)break;
d.pop();
}
}
public function mul10(x : int) : void
{
var r : Vector.<uint> = d.reverse();
for(var i : uint = 0;i < x;i++){
r.push(0);
}
d = r.reverse();
}
public function isZero() : Boolean
{
return d.length == 1 && d[0] == 0;
}
public function toNumber() : Number
{
return Number(toString());
}
public function toString() : String
{
return d.concat().reverse().join('');
}
}
