Mian-Chowla sequence: Difference between revisions
(Added VisualBasic.NET version) |
(Added C# version) |
||
Line 61: | Line 61: | ||
=={{header|C#|CSharp}}== |
|||
{{trans|Go}} |
|||
<lang csharp>using System; |
|||
using System.Linq; |
|||
static class Program { |
|||
public static int[] MianChowla(int n) { |
|||
int[] mc = new int[n - 1 + 1]; int[] sums = new int[] { 2 }; |
|||
int sum, le; mc[0] = 1; for (int i = 1; i <= n - 1; i++) { |
|||
le = sums.Length; for (int j = mc[i - 1] + 1; ; j++) { |
|||
mc[i] = j; for (int k = 0; k <= i; k++) { |
|||
if (sums.Contains(sum = mc[k] + j)) { |
|||
Array.Resize(ref sums, le); goto nxtJ; |
|||
} |
|||
Array.Resize(ref sums, sums.Length + 1); |
|||
sums[sums.Length - 1] = sum; |
|||
} |
|||
break; |
|||
nxtJ: ; |
|||
} |
|||
} |
|||
return mc; |
|||
} |
|||
public static void Main(string[] args) |
|||
{ |
|||
DateTime st = DateTime.Now; int[] mc = MianChowla(100); |
|||
Console.WriteLine("The first 30 terms of the Mian-Chowla sequence are:\n{0}", |
|||
string.Join(" ", mc.Take(30))); |
|||
Console.WriteLine("\nTerms 91 to 100 of the Mian-Chowla sequence are:\n{0}", |
|||
string.Join(" ", mc.Skip(90))); |
|||
Console.Write("\nComputation time was {0} seconds.", (DateTime.Now - st).TotalSeconds); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>The first 30 terms of the Mian-Chowla sequence are: |
|||
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312 |
|||
Terms 91 to 100 of the Mian-Chowla sequence are: |
|||
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 |
|||
Computation time was 1.1993837 seconds.</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
Revision as of 21:05, 14 March 2019
The Mian–Chowla sequence is an integer sequence defined recursively.
The sequence starts with:
- a1 = 1
then for n > 1, an is the smallest positive integer such that every pairwise sum
- ai + aj
is distinct, for all i and j less than or equal to n.
- The Task
- Find and display, here, on this page the first 30 terms of the Mian–Chowla sequence.
- Find and display, here, on this page the 91st through 100th terms of the Mian–Chowla sequence.
Demonstrating working through the first few terms longhand:
- a1 = 1
- 1 + 1 = 2
Speculatively try a2 = 2
- 1 + 1 = 2
- 1 + 2 = 3
- 2 + 2 = 4
There are no repeated sums so 2 is the next number in the sequence.
Speculatively try a3 = 3
- 1 + 1 = 2
- 1 + 2 = 3
- 1 + 3 = 4
- 2 + 2 = 4
- 2 + 3 = 5
- 3 + 3 = 6
Sum of 4 is repeated so 3 is rejected.
Speculatively try a3 = 4
- 1 + 1 = 2
- 1 + 2 = 3
- 1 + 4 = 5
- 2 + 2 = 4
- 2 + 4 = 6
- 4 + 4 = 8
There are no repeated sums so 4 is the next number in the sequence.
And so on...
- See also
C#
<lang csharp>using System; using System.Linq;
static class Program {
public static int[] MianChowla(int n) { int[] mc = new int[n - 1 + 1]; int[] sums = new int[] { 2 }; int sum, le; mc[0] = 1; for (int i = 1; i <= n - 1; i++) { le = sums.Length; for (int j = mc[i - 1] + 1; ; j++) { mc[i] = j; for (int k = 0; k <= i; k++) { if (sums.Contains(sum = mc[k] + j)) { Array.Resize(ref sums, le); goto nxtJ; } Array.Resize(ref sums, sums.Length + 1); sums[sums.Length - 1] = sum; } break; nxtJ: ; } } return mc; }
public static void Main(string[] args) { DateTime st = DateTime.Now; int[] mc = MianChowla(100); Console.WriteLine("The first 30 terms of the Mian-Chowla sequence are:\n{0}", string.Join(" ", mc.Take(30))); Console.WriteLine("\nTerms 91 to 100 of the Mian-Chowla sequence are:\n{0}", string.Join(" ", mc.Skip(90))); Console.Write("\nComputation time was {0} seconds.", (DateTime.Now - st).TotalSeconds); }
}</lang>
- Output:
The first 30 terms of the Mian-Chowla sequence are: 1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312 Terms 91 to 100 of the Mian-Chowla sequence are: 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 Computation time was 1.1993837 seconds.
Go
<lang go>package main
import "fmt"
func contains(is []int, s int) bool {
for _, i := range is { if s == i { return true } } return false
}
func mianChowla(n int) []int {
mc := make([]int, n) mc[0] = 1 is := []int{2} var sum int for i := 1; i < n; i++ { le := len(is) jloop: for j := mc[i-1] + 1; ; j++ { mc[i] = j for k := 0; k <= i; k++ { sum = mc[k] + j if contains(is, sum) { is = is[0:le] continue jloop } is = append(is, sum) } break } } return mc
}
func main() {
mc := mianChowla(100) fmt.Println("The first 30 terms of the Mian-Chowla sequence are:") fmt.Println(mc[0:30]) fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:") fmt.Println(mc[90:100])
}</lang>
- Output:
The first 30 terms of the Mian-Chowla sequence are: [1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312] Terms 91 to 100 of the Mian-Chowla sequence are: [22526 23291 23564 23881 24596 24768 25631 26037 26255 27219]
Perl
<lang perl>use strict; use warnings; use feature 'say';
sub generate_mc {
my($max) = @_; my $index = 0; my $test = 1; my %sums = (2 => 1); my @mc = 1; while ($test++) { my %these = %sums; map { next if ++$these{$_ + $test} > 1 } @mc[0..$index], $test; %sums = %these; $index++; return @mc if (push @mc, $test) > $max-1; }
}
my @mian_chowla = generate_mc(100); say "First 30 terms in the Mian–Chowla sequence:\n", join(' ', @mian_chowla[ 0..29]),
"\nTerms 91 through 100:\n", join(' ', @mian_chowla[90..99]);</lang>
- Output:
First 30 terms in the Mian–Chowla sequence: 1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312 Terms 91 through 100: 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Perl 6
<lang perl6>my @mian-chowla = 1, |(2..Inf).map: -> $test {
state $index = 1; state %sums = 2 => 1; my $next; my %these = %sums; (|@mian-chowla[^$index], $test).map: { ++$next and last if ++%these{$_ + $test} > 1 }; next if $next; %sums = %these; ++$index; $test
};
put 'First 30 terms in the Mian–Chowla sequence:'; put join ', ', @mian-chowla[^30];
put "\nTerms 91 through 100:"; put join ', ', @mian-chowla[90..99];</lang>
- Output:
First 30 terms in the Mian–Chowla sequence: 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312 Terms 91 through 100: 22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219
REXX
<lang rexx>/*REXX program computes and displays any range of the Mian─Chowla integer sequence. */ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI= 30 /* " " " " " " */ r.= 0 /*initialize the rekects stemmed array.*/ $=; if 1>=LO then $= 1 /*the Mian─Chowla sequence (so far)*/ @.=; @.1= 1 /*define start of the Mian─Chowla seq. */
- = 1 /*count of numbers in sequence (so far)*/
do t=2 until #>=HI; !.= 0 /*process numbers until range is filled*/ do i=1 for t; if r.i then iterate /*I already rejected? Then ignore it.*/ do j=i for t-i+1; if r.j then iterate /*J " " " " " */ _= i + j /*get sum; [↑] see if previously found*/ if !._ then do; r.t=1; iterate t; end /*reject T from the Mian─Chowla seq. */ !._= 1 /*mark _ as being one of the sums. */ end /*j*/ end /*i*/ #= # + 1; @.#= t /*bump counter; assign number to seq. */ if #>=LO & #<=HI then $= $ t /*In the specified range? Add to list.*/ end /*t*/
say 'The Mian─Chowla sequence for elements ' LO "──►" HI ' (inclusive):' say $</lang>
- output when using the default inputs:
The Mian─Chowla sequence for elements 1 ──► 30 (inclusive): 1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312
- output when using the input of: 91 100
The Mian─Chowla sequence for elements 91 ──► 100 (inclusive): 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Visual Basic .NET
<lang vbnet>Module Module1
Function MianChowla(ByVal n As Integer) As Integer() Dim mc As Integer() = New Integer(n - 1) {}, sums As Integer() = New Integer() {2} Dim sum, le As Integer : mc(0) = 1 : For i As Integer = 1 To n - 1 : le = sums.Length For j As Integer = mc(i - 1) + 1 To Integer.MaxValue mc(i) = j : For k As Integer = 0 To i sum = mc(k) + j : If sums.Contains(sum) Then Array.Resize(sums, le) : GoTo nxtJ Array.Resize(sums, sums.Length + 1) : sums(sums.Length - 1) = sum Next : Exit For nxtJ: Next : Next : Return mc End Function
Sub Main(ByVal args As String()) Dim st As DateTime = DateTime.Now, mc As Integer() = MianChowla(100) Console.WriteLine("The first 30 terms of the Mian-Chowla sequence are:" & _ vbLf & "{0}", String.Join(" ", mc.Take(30))) Console.WriteLine(vbLf & "Terms 91 to 100 of the Mian-Chowla sequence are:" & _ vbLf & "{0}", String.Join(" ", mc.Skip(90))) Console.Write(vbLf & "Computation time was {0} seconds.", (DateTime.Now - st).TotalSeconds) End Sub
End Module</lang>
- Output:
The first 30 terms of the Mian-Chowla sequence are: 1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312 Terms 91 to 100 of the Mian-Chowla sequence are: 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 Computation time was 1.1661764 seconds.