200229(2)

Crystal


A332800(2)

Conjecture についての計算は以下の通りです。

def a332800_conjecture(n)
  return 1 if n == 0
  a = (1..n).map{|i| [i]}
  len = 1
  while len < n
    b = Array(Array(Int32)).new
    a.each{|c|
      (1..n).each{|num|
        if !c.includes?(num)
          i = c.clone + [num]
          if len > 1
            if (i[-3] % i[-2]) < (i[-2] % i[-1])
              b << i
            end
          else
            b << i
          end
        end
      }
    }
    a = b
    len += 1
  end
  a.size
end

(0..19).each{|i| p a332800_conjecture(i)}

出力結果
1
1
2
3
4
6
7
9
11
13
14
19
20
22
25
29
30
36
37
42

200229

Crystal


A332800(1)

Crystal で計算してみた。途中で計算が止まる。

def a332800(n)
  return 1 if n == 0
  a = (1..n).map{|i| [i]}
  len = 1
  while len < n
    b = Array(Array(Int32)).new
    a.each{|c|
      (1..n).each{|num|
        if !c.includes?(num)
          i = c.clone + [num]
          if len > 1
            if (i[-3] % i[-2]) <= (i[-2] % i[-1])
              b << i
            end
          else
            b << i
          end
        end
      }
    }
    a = b
    len += 1
  end
  a.size
end

(0..20).each{|i| p a332800(i)}

出力結果
1
1
2
4
9
21
44
109
241
530
1176
3180
6456
14835
34672
81877
179434
479275
Program was killed

200227

Crystal


A318790

Crystal で計算してみた。

def check(d, a, i)
  return true if i == 0
  j = 1
  d_max = [i, d - 1].min
  while (a[i] - a[i - j]).abs >= d && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= d
end

def solve(d, len, a = Array(Int32).new)
  b = Array(Array(Int32)).new
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.includes?(m))
        if check(d, a + [m], s)
          b += solve(d, len, a + [m])
        end
      end
    }
  end
  b
end

def a318790(n)
  (1..n).map{|i| solve(i, i * i + 1).size // 2}
end

p a318790(4)

出力結果
[1, 7, 20, 37]

200226

Crystal


深さが不定の配列の作成

Ruby と違い型の設定が要る。

alias Ary = Int32 | String | Array(Ary)

a = Array(Ary).new
5.times{|i|
  a << i
  a << i.to_s
  p a
  b = Array(Ary).new
  b << a
  a = b
}

出力結果
[0, "0"]
[[0, "0"], 1, "1"]
[[[0, "0"], 1, "1"], 2, "2"]
[[[[0, "0"], 1, "1"], 2, "2"], 3, "3"]
[[[[[0, "0"], 1, "1"], 2, "2"], 3, "3"], 4, "4"]

200224

Crystal


A320843(2)

Crystal で計算してみた。

class Count
  @@cnt = 0
  def initialize
    @@cnt += 1
  end
  def self.instances
    @@cnt
  end
  def self.to_zero
    @@cnt = 0
  end
end

def search(a, num, n)
  if num == n + 1
    Count.new
  else
    (1..n).each{|i|
      if a[i] == 0
        if num % i == 0 || i % num == 0
          a[i] = num
          search(a, num + 1, n)
          a[i] = 0
        end
      end
    }
  end
end

def a320843(n)
  a = [0] * (n + 1)
  Count.to_zero
  search(a, 1, n)
  Count.instances
end

p (0..20).map{|i| a320843(i)}

出力結果
[1, 1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679, 87328, 90478, 435812, 449586, 1939684]

200215

Ruby


素数の個数(8)

150709分をRuby2.7で

ruby --jit ○○.rb

とするだけで、10分くらいで計算が終わった。

200209

Crystal


素数の和(2)

以前のRuby のコードをCrystal のコードにかえて出力してみた。

require "big"

def sum_of_primes(n)
  m = Math.sqrt(n).to_i
  keys = (1..m).map{|i| n // i}
  keys += (1..keys[-1] - 1).to_a.reverse
  h = Hash(Int32, BigInt).new
  keys.each{|i|
    j = i.to_big_i
    h[i] = j * (j + 1) // 2 - 1
  }
  (2..m).each{|i|
    if h[i] > h[i - 1] # このときiは素数
      hp = h[i - 1]
      i2 = i * i
        keys.each{|j|
          break if j < i2
          h[j] -= i * (h[j // i] - hp)
        }
    end
  }
  h[n]
end

time = Time.local
p (0..9).map{|i| sum_of_primes(10 ** i)}
puts Time.local - time

出力結果
[0, 17, 1060, 76127, 5736396, 454396537, 37550402023, 3203324994356, 279209790387276, 24739512092254535]
00:00:02.812922000

200208(2)

Crystal


A006880とA046731(2)

10^n までの素数の数と和を出力してみた。

require "big"

def a006880(n)
  max = 10 ** n - 1
  ary = Array.new(max + 1, true)

  i = 2
  while i * i <= max
    if ary[i]
      (2 * i).step(to: max, by: i){|j| ary[j] = false}
    end
    i += 1
  end

  s = 0.to_big_i
  (2..max).each{|i| s += 1 if ary[i]}
  p s
end

def a046731(n)
  max = 10 ** n - 1
  ary = Array.new(max + 1, true)

  i = 2
  while i * i <= max
    if ary[i]
      (2 * i).step(to: max, by: i){|j| ary[j] = false}
    end
    i += 1
  end

  s = 0.to_big_i
  (2..max).each{|i| s += i if ary[i]}
  p s
end

n = 8
p (0..n).map{|i| a006880(i)}
p (0..n).map{|i| a046731(i)}

出力結果
0
4
25
168
1229
9592
78498
664579
5761455
[0, 4, 25, 168, 1229, 9592, 78498, 664579, 5761455]
0
17
1060
76127
5736396
454396537
37550402023
3203324994356
279209790387276
[0, 17, 1060, 76127, 5736396, 454396537, 37550402023, 3203324994356, 279209790387276]

200208

Crystal


フィボナッチ数列(2)

Crystal で計算してみた。
require のあとはシングルクォーテーションだとだめなようだ。

require "big"

struct BigInt
  def add!(other : BigInt) : BigInt
    LibGMP.add(self, self, other)
    self
  end
end

def fib(n)
  a = 0.to_big_i
  b = 1.to_big_i
  n.times{|i|
    a.add!(b)
    a, b = b, a
    puts "#{i + 1} : #{a}"
  }
end

time = Time.local
fib(100)
puts Time.local - time

出力結果
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8
7 : 13
8 : 21
9 : 34
10 : 55
11 : 89
12 : 144
13 : 233
14 : 377
15 : 610
16 : 987
17 : 1597
18 : 2584
19 : 4181
20 : 6765
21 : 10946
22 : 17711
23 : 28657
24 : 46368
25 : 75025
26 : 121393
27 : 196418
28 : 317811
29 : 514229
30 : 832040
31 : 1346269
32 : 2178309
33 : 3524578
34 : 5702887
35 : 9227465
36 : 14930352
37 : 24157817
38 : 39088169
39 : 63245986
40 : 102334155
41 : 165580141
42 : 267914296
43 : 433494437
44 : 701408733
45 : 1134903170
46 : 1836311903
47 : 2971215073
48 : 4807526976
49 : 7778742049
50 : 12586269025
51 : 20365011074
52 : 32951280099
53 : 53316291173
54 : 86267571272
55 : 139583862445
56 : 225851433717
57 : 365435296162
58 : 591286729879
59 : 956722026041
60 : 1548008755920
61 : 2504730781961
62 : 4052739537881
63 : 6557470319842
64 : 10610209857723
65 : 17167680177565
66 : 27777890035288
67 : 44945570212853
68 : 72723460248141
69 : 117669030460994
70 : 190392490709135
71 : 308061521170129
72 : 498454011879264
73 : 806515533049393
74 : 1304969544928657
75 : 2111485077978050
76 : 3416454622906707
77 : 5527939700884757
78 : 8944394323791464
79 : 14472334024676221
80 : 23416728348467685
81 : 37889062373143906
82 : 61305790721611591
83 : 99194853094755497
84 : 160500643816367088
85 : 259695496911122585
86 : 420196140727489673
87 : 679891637638612258
88 : 1100087778366101931
89 : 1779979416004714189
90 : 2880067194370816120
91 : 4660046610375530309
92 : 7540113804746346429
93 : 12200160415121876738
94 : 19740274219868223167
95 : 31940434634990099905
96 : 51680708854858323072
97 : 83621143489848422977
98 : 135301852344706746049
99 : 218922995834555169026
100 : 354224848179261915075
00:00:00.000445000