First perfect square in base n with n unique digits: Difference between revisions
First perfect square in base n with n unique digits (view source)
Revision as of 21:37, 23 June 2019
, 4 years ago→{{header|C#|Csharp}}: fixed problem with base28
m (→{{header|C#|Csharp}}: oops, problem with base 28, will fix later) |
(→{{header|C#|Csharp}}: fixed problem with base28) |
||
Line 174:
// parse a string into a BigInteger, using current base
static BigInteger to10(string s) {
BigInteger res = 0; foreach (char i in s) res = res * Base + chars.IndexOf(i);
res = res * Base + chars.IndexOf(i);▼
return res;
}
Line 181 ⟶ 180:
// returns the minimum value string, optionally inserting extra digit
static string fixup(int n) {
string res = chars.Substring(0, Base); if (n > 0) res = res.Insert(n, n.ToString());
return "10" + res.Substring(2);
}
Line 188 ⟶ 186:
// checks the square against the threshold, advances various limits when needed
static void check(BigInteger sq) {
if (sq > threshold
}
}
// performs all the caclulations for the current base
static void doOne() {
limits = new List<BigInteger>();
bmo = (byte)(Base - 1); byte dr = 0; if ((Base & 1) == 1) dr = (byte)(Base >> 1);
Line 203 ⟶ 200:
byte[] sdr = new byte[bmo]; byte rc = 0; for (i = 0; i < bmo; i++) {
sdr[i] = (byte)((i * i) % bmo); rc += sdr[i] == dr ? (byte)1 : (byte)0;
sdr[i] += sdr[i] == 0 ? bmo : (byte)0
} i = 0; if (dr > 0) {
for (i = 1; i <= dr; i++) if (sdr[i] >= dr) if (id > sdr[i]) id = sdr[i]; id -= dr;
i = 0
} ms = fixup(id);
BigInteger sq = to10(ms); BigInteger rt = new BigInteger(Math.Sqrt((double)sq) + 1);
sq = rt * rt; if (Base > 9) {
for (int j = 1; j < Base; j++)
limits.Add(to10(ms.Substring(0, j) + new string(chars[bmo], Base - j + (rc > 0 ? 0 : 1))));
limits.Reverse(); while (sq < limits[0]) { rt++; sq = rt * rt; }
Line 213 ⟶ 214:
BigInteger dn = (rt << 1) + 1; BigInteger d = 1; if (Base > 3 && rc > 0) {
while (sq % bmo != dr) { rt += 1; sq += dn; dn += 2; } // alligns sq to dr
inc = bmo / rc;
if (inc > 1) { dn += rt * (inc - 2) - 1; d = inc * inc; }
dn += dn + d;
}
d <<= 1; if (Base > 9) {
blim = 0; while (sq < limits[bmo - blim - 1]) blim++; ic = (byte)(blim + 1);
threshold = limits[bmo - blim - 1];
if (blim > 0) for (byte j = 0; j <
if (blim > 0) bllim = to10(ms.Substring(0, blim + 1)); else bllim = 0;
if (Base > 5 && rc > 0)
Line 231 ⟶ 234:
} rt += i * inc;
Console.WriteLine("{0,3} {1,2} {2,2} {3,20} -> {4,-40} {5,10} {6,9:0.0000}s {7,9:0.0000}s",
Base, inc, (id > 0 ? chars.Substring(id, 1) : " "), toStr(rt), toStr(sq), i,
(DateTime.Now - st).TotalSeconds, (DateTime.Now - st0).TotalSeconds);
}
Line 238 ⟶ 241:
Console.WriteLine("base inc id root square" +
" test count time total");
for (Base = 2; Base <=
Console.WriteLine("Elasped time was {0,8:0.00} minutes", (DateTime.Now - st0).TotalMinutes);
}
Line 250 ⟶ 253:
6 5 523 -> 452013 20 0.0000s 0.0060s
7 6 1431 -> 2450361 34 0.0000s 0.0060s
8 7 3344 -> 13675420 41 0.
9 4 11642 -> 136802574 289 0.
10 3 32043 -> 1026753849 17 0.
11 10 111453 -> 1240A536789 1498 0.0010s 0.
12 11 3966B9 -> 124A7B538609 6883 0.
13 1 3 3828943 -> 10254773CA86B9 8242 0.
14 13 3A9DB7C -> 10269B8C57D3A4 1330 0.
15 14 1012B857 -> 102597BACE836D4 4216 0.0020s 0.
16 15 404A9D9B -> 1025648CFEA37BD9 18457 0.0100s 0.
17 1 1 423F82GA9 -> 101246A89CGFB357ED 195112 0.
18 17 44B482CAD -> 10236B5F8EG4AD9CH7 30440 0.
19 6 1011B55E9A -> 10234DHBG7CI8F6A9E5 93021 0.
20 19 49DGIH5D3G -> 1024E7CDI3HB695FJA8G 11310604
21 1 6 4C9HE5FE27F -> 1023457DG9HI8J6B6KCEAF 601843 1.
22 21 4F94788GJ0F -> 102369FBGDEJ48CHI7LKA5 27804949 18.
23 22 1011D3EL56MC -> 10234ACEDKG9HM8FBJIL756 17710217
24 23 4LJ0HDGF0HD3 -> 102345B87HFECKJNIGMDLA69 4266555 2.
25 12 1011E145FHGHM -> 102345DOECKJ6GFB8LIAM7NH9 78092124
26 5 52K8N53BDM99K -> 1023458LO6IEMKG79FPCHNJDBA 402922568
27 26 1011F11E37OBJJ -> 1023458ELOMDHBIJFGKP7CQ9N6A 457555293
28 9 58A3CKP3N4CQD7 -> 1023456CGJBIRQEDHP98KMOAN7FL 749592976 508.4498s 1215.9292s
Elasped time was 20.27 minutes
</pre>
| |||