Hofstadter-Conway $10,000 sequence: Difference between revisions

Content added Content deleted
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 679: Line 679:
Maximum between 2^19 and 2^20 was 0.533779</pre>
Maximum between 2^19 and 2^20 was 0.533779</pre>


=={{header|C++}}==
<lang cpp>
#include <deque>
#include <iostream>

int hcseq(int n)
{
static std::deque<int> seq(2, 1);
while (seq.size() < n)
{
int x = seq.back();
seq.push_back(seq[x-1] + seq[seq.size()-x]);
}
return seq[n-1];
}

int main()
{
int pow2 = 1;
for (int i = 0; i < 20; ++i)
{
int pow2next = 2*pow2;
double max = 0;
for (int n = pow2; n < pow2next; ++n)
{
double anon = hcseq(n)/double(n);
if (anon > max)
max = anon;
}
std::cout << "maximum of a(n)/n between 2^" << i
<< " (" << pow2 << ") and 2^" << i+1
<< " (" << pow2next << ") is " << max << "\n";
pow2 = pow2next;
}
}
</lang>
Output:
<pre>
maximum of a(n)/n between 2^0 (1) and 2^1 (2) is 1
maximum of a(n)/n between 2^1 (2) and 2^2 (4) is 0.666667
maximum of a(n)/n between 2^2 (4) and 2^3 (8) is 0.666667
maximum of a(n)/n between 2^3 (8) and 2^4 (16) is 0.636364
maximum of a(n)/n between 2^4 (16) and 2^5 (32) is 0.608696
maximum of a(n)/n between 2^5 (32) and 2^6 (64) is 0.590909
maximum of a(n)/n between 2^6 (64) and 2^7 (128) is 0.576087
maximum of a(n)/n between 2^7 (128) and 2^8 (256) is 0.567416
maximum of a(n)/n between 2^8 (256) and 2^9 (512) is 0.559459
maximum of a(n)/n between 2^9 (512) and 2^10 (1024) is 0.554937
maximum of a(n)/n between 2^10 (1024) and 2^11 (2048) is 0.550101
maximum of a(n)/n between 2^11 (2048) and 2^12 (4096) is 0.547463
maximum of a(n)/n between 2^12 (4096) and 2^13 (8192) is 0.544145
maximum of a(n)/n between 2^13 (8192) and 2^14 (16384) is 0.542443
maximum of a(n)/n between 2^14 (16384) and 2^15 (32768) is 0.540071
maximum of a(n)/n between 2^15 (32768) and 2^16 (65536) is 0.538784
maximum of a(n)/n between 2^16 (65536) and 2^17 (131072) is 0.537044
maximum of a(n)/n between 2^17 (131072) and 2^18 (262144) is 0.53602
maximum of a(n)/n between 2^18 (262144) and 2^19 (524288) is 0.534645
maximum of a(n)/n between 2^19 (524288) and 2^20 (1048576) is 0.533779
</pre>
=={{header|C sharp|C#}}==
=={{header|C sharp|C#}}==
{{works with|C#|3.0}}
{{works with|C#|3.0}}
Line 808: Line 749:
The winning number is 1489.
The winning number is 1489.
</pre>
</pre>

=={{header|C++}}==
<lang cpp>
#include <deque>
#include <iostream>

int hcseq(int n)
{
static std::deque<int> seq(2, 1);
while (seq.size() < n)
{
int x = seq.back();
seq.push_back(seq[x-1] + seq[seq.size()-x]);
}
return seq[n-1];
}

int main()
{
int pow2 = 1;
for (int i = 0; i < 20; ++i)
{
int pow2next = 2*pow2;
double max = 0;
for (int n = pow2; n < pow2next; ++n)
{
double anon = hcseq(n)/double(n);
if (anon > max)
max = anon;
}
std::cout << "maximum of a(n)/n between 2^" << i
<< " (" << pow2 << ") and 2^" << i+1
<< " (" << pow2next << ") is " << max << "\n";
pow2 = pow2next;
}
}
</lang>
Output:
<pre>
maximum of a(n)/n between 2^0 (1) and 2^1 (2) is 1
maximum of a(n)/n between 2^1 (2) and 2^2 (4) is 0.666667
maximum of a(n)/n between 2^2 (4) and 2^3 (8) is 0.666667
maximum of a(n)/n between 2^3 (8) and 2^4 (16) is 0.636364
maximum of a(n)/n between 2^4 (16) and 2^5 (32) is 0.608696
maximum of a(n)/n between 2^5 (32) and 2^6 (64) is 0.590909
maximum of a(n)/n between 2^6 (64) and 2^7 (128) is 0.576087
maximum of a(n)/n between 2^7 (128) and 2^8 (256) is 0.567416
maximum of a(n)/n between 2^8 (256) and 2^9 (512) is 0.559459
maximum of a(n)/n between 2^9 (512) and 2^10 (1024) is 0.554937
maximum of a(n)/n between 2^10 (1024) and 2^11 (2048) is 0.550101
maximum of a(n)/n between 2^11 (2048) and 2^12 (4096) is 0.547463
maximum of a(n)/n between 2^12 (4096) and 2^13 (8192) is 0.544145
maximum of a(n)/n between 2^13 (8192) and 2^14 (16384) is 0.542443
maximum of a(n)/n between 2^14 (16384) and 2^15 (32768) is 0.540071
maximum of a(n)/n between 2^15 (32768) and 2^16 (65536) is 0.538784
maximum of a(n)/n between 2^16 (65536) and 2^17 (131072) is 0.537044
maximum of a(n)/n between 2^17 (131072) and 2^18 (262144) is 0.53602
maximum of a(n)/n between 2^18 (262144) and 2^19 (524288) is 0.534645
maximum of a(n)/n between 2^19 (524288) and 2^20 (1048576) is 0.533779
</pre>

=={{header|Clojure}}==
=={{header|Clojure}}==
<lang Clojure>(ns rosettacode.hofstader-conway
<lang Clojure>(ns rosettacode.hofstader-conway
Line 1,005: Line 1,007:
→ 1489 ;; Mallows number
→ 1489 ;; Mallows number
</pre>
</pre>



=={{header|Eiffel}}==
=={{header|Eiffel}}==
Line 1,182: Line 1,183:
1489
1489
</lang>
</lang>

=={{header|F Sharp|F#}}==
=={{header|F Sharp|F#}}==
<lang fsharp>let a = ResizeArray[0; 1; 1]
<lang fsharp>let a = ResizeArray[0; 1; 1]
Line 1,333: Line 1,335:
Mallows number = 1489
Mallows number = 1489
</pre>
</pre>

=={{header|FreeBASIC}}==
=={{header|FreeBASIC}}==
{{trans|BBC BASIC}}
{{trans|BBC BASIC}}
Line 1,611: Line 1,614:
MxAnN@AnN@hc10kE 20
MxAnN@AnN@hc10kE 20
1 0.666667 0.666667 0.636364 ...</lang>
1 0.666667 0.666667 0.636364 ...</lang>

=={{header|Java}}==
=={{header|Java}}==


Line 2,077: Line 2,081:
Maximum between 2^19 and 2^20 was 0.53377923
Maximum between 2^19 and 2^20 was 0.53377923
</pre>
</pre>



=={{header|Oforth}}==
=={{header|Oforth}}==
Line 2,185: Line 2,188:
<pre>%1 = [2/3, 2/3, 7/11, 14/23, 13/22, 53/92, 101/178, 207/370, 399/719, 818/1487, 1586/2897, 3248/5969, 6320/11651, 12002/22223, 24290/45083, 24037/44758, 97226/181385, 189095/353683, 385703/722589]
<pre>%1 = [2/3, 2/3, 7/11, 14/23, 13/22, 53/92, 101/178, 207/370, 399/719, 818/1487, 1586/2897, 3248/5969, 6320/11651, 12002/22223, 24290/45083, 24037/44758, 97226/181385, 189095/353683, 385703/722589]
%2 = 1489</pre>
%2 = 1489</pre>

=={{header|Pascal}}==
=={{header|Pascal}}==
tested with freepascal 3.1.1 64 Bit.
tested with freepascal 3.1.1 64 Bit.
Line 2,374: Line 2,378:
The prize would have been won at 1489 !
The prize would have been won at 1489 !
</pre>
</pre>

=={{header|Perl 6}}==
{{works with|Rakudo|2018.09}}
Note that <tt>@a</tt> is a lazy array, and the Z variants are "zipwith" operators.
<lang perl6>my $n = 3;
my @a = (0,1,1, -> $p { @a[$p] + @a[$n++ - $p] } ... *);
@a[2**20]; # pre-calculate sequence

my $last55;
for 1..19 -> $power {
my @range := 2**$power .. 2**($power+1)-1;
my @ratios = (@a[@range] Z/ @range) Z=> @range;
my $max = @ratios.max;
($last55 = .value if .key >= .55 for @ratios) if $max.key >= .55;
say $power.fmt('%2d'), @range.min.fmt("%10d"), '..', @range.max.fmt("%-10d"),
$max.key, ' at ', $max.value;
}
say "Mallows' number would appear to be ", $last55;</lang>
{{out}}
<pre> 1 2..3 0.666666666666667 at 3
2 4..7 0.666666666666667 at 6
3 8..15 0.636363636363636 at 11
4 16..31 0.608695652173913 at 23
5 32..63 0.590909090909091 at 44
6 64..127 0.576086956521739 at 92
7 128..255 0.567415730337079 at 178
8 256..511 0.559459459459459 at 370
9 512..1023 0.554937413073713 at 719
10 1024..2047 0.550100874243443 at 1487
11 2048..4095 0.547462892647566 at 2897
12 4096..8191 0.544144747863964 at 5969
13 8192..16383 0.542442708780362 at 11651
14 16384..32767 0.540071097511587 at 22223
15 32768..65535 0.538784020584256 at 45083
16 65536..131071 0.537043656999866 at 89516
17 131072..262143 0.536020067811561 at 181385
18 262144..524287 0.534645431078112 at 353683
19 524288..1048575 0.533779229963368 at 722589
Mallows' number would appear to be 1489</pre>


=={{header|Phix}}==
=={{header|Phix}}==
Line 2,731: Line 2,696:
Max. between 2^19 and 2^20 is 0.53378 at 722589
Max. between 2^19 and 2^20 is 0.53378 at 722589
Mallows number: 1489</pre>
Mallows number: 1489</pre>

=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.09}}
Note that <tt>@a</tt> is a lazy array, and the Z variants are "zipwith" operators.
<lang perl6>my $n = 3;
my @a = (0,1,1, -> $p { @a[$p] + @a[$n++ - $p] } ... *);
@a[2**20]; # pre-calculate sequence

my $last55;
for 1..19 -> $power {
my @range := 2**$power .. 2**($power+1)-1;
my @ratios = (@a[@range] Z/ @range) Z=> @range;
my $max = @ratios.max;
($last55 = .value if .key >= .55 for @ratios) if $max.key >= .55;
say $power.fmt('%2d'), @range.min.fmt("%10d"), '..', @range.max.fmt("%-10d"),
$max.key, ' at ', $max.value;
}
say "Mallows' number would appear to be ", $last55;</lang>
{{out}}
<pre> 1 2..3 0.666666666666667 at 3
2 4..7 0.666666666666667 at 6
3 8..15 0.636363636363636 at 11
4 16..31 0.608695652173913 at 23
5 32..63 0.590909090909091 at 44
6 64..127 0.576086956521739 at 92
7 128..255 0.567415730337079 at 178
8 256..511 0.559459459459459 at 370
9 512..1023 0.554937413073713 at 719
10 1024..2047 0.550100874243443 at 1487
11 2048..4095 0.547462892647566 at 2897
12 4096..8191 0.544144747863964 at 5969
13 8192..16383 0.542442708780362 at 11651
14 16384..32767 0.540071097511587 at 22223
15 32768..65535 0.538784020584256 at 45083
16 65536..131071 0.537043656999866 at 89516
17 131072..262143 0.536020067811561 at 181385
18 262144..524287 0.534645431078112 at 353683
19 524288..1048575 0.533779229963368 at 722589
Mallows' number would appear to be 1489</pre>


=={{header|REXX}}==
=={{header|REXX}}==
Line 3,267: Line 3,272:
Maximum in range 524288 to 1048576 occurs at 722589: 0,533779
Maximum in range 524288 to 1048576 occurs at 722589: 0,533779
Mallows number is 1489 </pre>
Mallows number is 1489 </pre>

=={{header|X86 Assembly}}==
=={{header|X86 Assembly}}==
Using FASM syntax.
Using FASM syntax.
Retrieved from "https://rosettacode.org/wiki/Hofstadter-Conway_$10,000_sequence"