Minimum positive multiple in base 10 using only 0 and 1: Difference between revisions
Minimum positive multiple in base 10 using only 0 and 1 (view source)
Revision as of 06:26, 27 September 2020
, 3 years agoadded C# version based on the C code for the 'Binary' Puzzle algorithm, linked from OEIS
(added C# version based on the C code for the 'Binary' Puzzle algorithm, linked from OEIS) |
|||
Line 342:
2997 * 370740777814851888925963 = 1111110111111111111111111111
4878 * 20500412076896496722245 = 100001010111101111011111110</pre>
=={{header|C#|Csharp}}==
Translated from the C code for the 'Binary' Puzzle algorithm, from the OEIS link. Note that since this task asks for a maximum of 28 digits for "B10", that only a 32 bit integer is required, even though the original code uses 64 bit integers. Not a huge point, but performance is noticeably improved.
Since C# has a ''decimal'' type, it can be used instead of an external 128 bit integer package to compute the multiplier.
<lang csharp>using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
class Program {
static string fmt = "{0,4} * {1,24} = {2,-28}\n";
static void B10(int n) { if (n <= 1) return;
int[] pow = new int[++n], val = new int[n--];
int count = 0, ten = 1, x = 1; for (; x <= n; x++) {
val[x] = ten; for (int j = 0; j <= n; j++)
if (pow[j] != 0 && pow[(j + ten) % n] == 0 && pow[j] != x)
pow[(j + ten) % n] = x; if (pow[ten] == 0) pow[ten] = x;
ten = (10 * ten) % n; if (pow[0] != 0) { x = n;
string s = ""; while (x != 0) { int p = pow[x % n];
if (count > p) s += new string('0', (int)(count - p));
count = p - 1; s += "1"; x = (n + x - val[p]) % n; }
if (count > 0) s += new string('0', (int)count);
Write(fmt, n, decimal.Parse(s) / n, s);
return; } } Write("Can't do it!"); }
static void Main(string[] args) {
var st = DateTime.Now; List<int> m = new List<int> {
297,576,594,891,909,999,1998,2079,2251,2277,2439,2997,4878};
Write(fmt, "n", "multiplier", "B10");
WriteLine(new string('-', 62)); Write(fmt, 1, 1, 1);
for (int n = 1; n <= m.Last(); n++)
if (n <= 10 || n >= 95 && n <= 105 || m.Contains(n))
B10(n); WriteLine("\nTook {0}ms",
(DateTime.Now - st).TotalMilliseconds); }
}</lang>
{{out}}
<pre> n * multiplier = B10
--------------------------------------------------------------
1 * 1 = 1
2 * 5 = 10
3 * 37 = 111
4 * 25 = 100
5 * 2 = 10
6 * 185 = 1110
7 * 143 = 1001
8 * 125 = 1000
9 * 12345679 = 111111111
10 * 1 = 10
95 * 1158 = 110010
96 * 115625 = 11100000
97 * 114433 = 11100001
98 * 112245 = 11000010
99 * 1122334455667789 = 111111111111111111
100 * 1 = 100
101 * 1 = 101
102 * 9805 = 1000110
103 * 107767 = 11100001
104 * 9625 = 1001000
105 * 962 = 101010
297 * 3740778151889263 = 1111011111111111111
576 * 192901234375 = 111111111000000
594 * 18703890759446315 = 11110111111111111110
891 * 1247038284075321 = 1111111111111111011
909 * 1112333455567779 = 1011111111111111111
999 * 111222333444555666777889 = 111111111111111111111111111
1998 * 556111667222778333889445 = 1111111111111111111111111110
2079 * 481530111164555609 = 1001101101111111111111
2251 * 44913861 = 101101101111
2277 * 4879275850290343 = 11110111111111111011
2439 * 4100082415379299344449 = 10000101011110111101111111
2997 * 370740777814851888925963 = 1111110111111111111111111111
4878 * 20500412076896496722245 = 100001010111101111011111110
Took 10.3014ms
</pre>Timing from tio.run
=={{header|C++}}==
| |||