Class: Integer

Inherits:
Object
  • Object
show all
Defined in:
lib/include/integer.rb

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.*(other) ⇒ Object

Raises:

  • (ArgumentError) 


11
12
13
14
 
# File 'lib/include/integer.rb', line 11

def *(other)
	raise ArgumentError unless other.kind_of?(self)
	Abst::IntegerIdeal.new(other)
end

./(other) ⇒ Object 



16
17
18
19
20
21
22
23
 
# File 'lib/include/integer.rb', line 16

def /(other)
	if other.kind_of?(Integer)
		other = Integer * other
	else
		raise ArgumentError unless other.kind_of?(Abst::IntegerIdeal)
	end
	return residue_class(other)
end

.coerce(other) ⇒ Object 



25
26
27
 
# File 'lib/include/integer.rb', line 25

def coerce(other)
	return [self, other]
end

.one ⇒ Object 



7
8
9
 
# File 'lib/include/integer.rb', line 7

def one
	return 1
end

.to_tex ⇒ Object 



29
30
31
 
# File 'lib/include/integer.rb', line 29

def to_tex
	return "\\mathbb{Z}"
end

.zero ⇒ Object 



3
4
5
 
# File 'lib/include/integer.rb', line 3

def zero
	return 0
end

Instance Method Details

#bit_size ⇒ Object 



34
35
36
 
# File 'lib/include/integer.rb', line 34

def bit_size
	return Abst.ilog2(self) + 1
end

#combination(r) ⇒ Object Also known as: C 



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/include/integer.rb', line 81

def combination(r)
	r = self - r if self - r < r

	if r <= 0
		return 1 if 0 == r
		return 0
	end

	rslt = self
	2.upto(r) do |i|
		rslt = rslt * (self - i + 1) / i
	end

	return rslt
end

#extended_pmod_factorial(prime) ⇒ Object

Param

prime

Return

integer f > 0 and e >= 0 s.t. prime ** e || self! and f == self! / (prime ** e) % prime



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/include/integer.rb', line 63

def extended_pmod_factorial(prime)
	q, r = self.divmod prime
	fac = q.even? ? 1 : prime - 1
	fac = fac * r.pmod_factorial(prime) % prime

	a = nil
	e = q
	if prime <= q
		a, b = q.extended_pmod_factorial(prime)
		e += b
	else
		a = q.pmod_factorial(prime)
	end
	fac = fac * a % prime

	return fac, e
end

#factorial ⇒ Object

Param

non-negative integer self

Return

factorial self!



45
46
47
 
# File 'lib/include/integer.rb', line 45

def factorial
	return 2.upto(self).inject(1, &:*)
end

#heptagonal? ⇒ Boolean

Heptagonal numbers are generated by the formula, P7_n = n * (5 * n - 3) / 2 The first ten heptagonal numbers are:

1, 7, 18, 34, 55
Return

integer n s.t. self == P7_n if exist else false

Returns:

  • (Boolean) 


231
232
233
234
235
236
237
238
 
# File 'lib/include/integer.rb', line 231

def heptagonal?
	return false unless r = (self * 40 + 9).square?

	q, r = (3 + r).divmod(10)
	return false unless 0 == r

	return q
end

#hexagonal? ⇒ Boolean

Hexagonal numbers are generated by the formula, H_n = n * (2 * n - 1) The first ten hexagonal numbers are:

1, 6, 15, 28, 45, 66, 91, 120, 153, 190, ...
Return

integer n s.t. self == H_n if exist else false

Returns:

  • (Boolean) 


220
221
222
223
224
225
 
# File 'lib/include/integer.rb', line 220

def hexagonal?
	return false unless r = ((self << 3) + 1).square?
	return false unless 0 == (1 + r) & 3

	return (1 + r) >> 2
end

#inverse ⇒ Object 



49
50
51
 
# File 'lib/include/integer.rb', line 49

def inverse
	return 1 / Rational(self)
end

#octagonal? ⇒ Boolean

Octagonal numbers are generated by the formula, P8_n = n * (3 * n - 2) The first ten octagonal numbers are:

1, 8, 21, 40, 65, ...
Return

integer n s.t. self == P7_n if exist else false

Returns:

  • (Boolean) 


244
245
246
247
248
249
250
251
 
# File 'lib/include/integer.rb', line 244

def octagonal?
	return false unless r = (self * 3 + 1).square?

	q, r = (1 + r).divmod(3)
	return false unless 0 == r

	return q
end

#pentagonal? ⇒ Boolean

Pentagonal numbers are generated by the formula, P_n = n * (3 * n - 1) / 2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
Return

integer n s.t. self == P_n if exist else false

Returns:

  • (Boolean) 


207
208
209
210
211
212
213
214
 
# File 'lib/include/integer.rb', line 207

def pentagonal?
	return false unless r = (24 * self + 1).square?

	q, r = (1 + r).divmod(6)
	return false unless 0 == r

	return q
end

#pmod_combination(r, prime) ⇒ Object 



98
99
100
101
102
103
104
105
 
# File 'lib/include/integer.rb', line 98

def pmod_combination(r, prime)
	f1, e1 = self.extended_pmod_factorial(prime)
	f2, e2 = r.extended_pmod_factorial(prime)
	f3, e3 = (self - r).extended_pmod_factorial(prime)

	return 0 if e2 + e3 < e1
	return f1 * Abst.inverse(f2 * f3, prime) % prime
end

#pmod_factorial(prime) ⇒ Object

Param

prime

Return

self! mod prime



55
56
57
 
# File 'lib/include/integer.rb', line 55

def pmod_factorial(prime)
	return 2.upto(self).inject(1) {|r, i| r * i % prime}
end

#power_of?(m) ⇒ Boolean

Returns boolean whether self is power of m or not.

Parameters:

  • positive —

    integer m > 1

Returns:

  • (Boolean) —

    boolean whether self is power of m or not



114
115
116
117
118
119
120
121
122
 
# File 'lib/include/integer.rb', line 114

def power_of?(m)
	n = self
	until 1 == n
		n, r = n.divmod(m)
		return false unless 0 == r
	end

	return true
end

#repeated_combination(r) ⇒ Object Also known as: H 



107
108
109
 
# File 'lib/include/integer.rb', line 107

def repeated_combination(r)
	return (self + r - 1).combination(r)
end

#square? ⇒ Boolean

Test whether self is a square number or not

Param

positive integer self

Return

square root of self if self is square else false

Returns:

  • (Boolean) 


138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/include/integer.rb', line 138

def square?
	check = {
		11=>[true, true, false, true, true, true, false, false, false, true, false],
		63=>[true, true, false, false, true, false, false, true, false, true, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, true, false, false, true, false, false, false, false, false, false, false, true, true, false, false, false, false, false, true, false, false, true, false, false, true, false, false, false, false, false, false, false, false, true,false, false, false, false],
		64=>[true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false,false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false],
		65=>[true, true, false, false, true, false, false, false, false, true, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, true, true, false, false, true, true, false, false, false, false, true, true, false, false, true, true, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, true, false, false, false, false, true, false, false, true]
	}

	# 64
	t = self & 63
	return false unless check[64][t]

	r = self % 45045	# == 63 * 65 * 11
	[63, 65, 11].each do |c|
		return false unless check[c][r % c]
	end

	q = Abst.isqrt(self)
	return false unless q ** 2 == self

	return q
end

#squarefree? ⇒ Boolean

Param

positive integer self

Return

true if self is squarefree, false otherwise

Returns:

  • (Boolean) 


164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/include/integer.rb', line 164

def squarefree?
	n = self
	if n.even?
		return false if 0 == n[1]
		n >>= 1
	end

	return true if self <= 3
	return false if self.square?

	pl = Abst.primes_list

	# trial division
	limit = Abst.isqrt(n)
	1.upto(pl.size - 1).each do |i|
		d = pl[i]
		return true if limit < d

		if n % d == 0
			n /= d
			return false if n % d == 0
			limit = Abst.isqrt(n)
		end
	end

	d = pl.last + 2
	loop do
		return true if limit < d

		if n % d == 0
			n /= d
			return false if n % d == 0
			limit = Abst.isqrt(n)
		end

		d += 2
	end
end

#to_fs ⇒ Object

Return

formatted string



39
40
41
 
# File 'lib/include/integer.rb', line 39

def to_fs
	return self.to_s.gsub(/(?<=\d)(?=(\d\d\d)+$)/, ' ')
end

#triangle? ⇒ Boolean

Triangle numbers are generated by the formula, T_n = n * (n + 1) / 2. The first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Return

integer n s.t. self == T_n if exist else false

Returns:

  • (Boolean) 


128
129
130
131
132
133
 
# File 'lib/include/integer.rb', line 128

def triangle?
	return false unless r = ((self << 3) + 1).square?
	return false unless (r - 1).even?

	return (r - 1) >> 1
end