Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

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

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

""" 

FLINT Arithmetic Functions 

""" 

  

#***************************************************************************** 

# Copyright (C) 2013 Fredrik Johansson <fredrik.johansson@gmail.com> 

# 

# This program is free software: you can redistribute it and/or modify 

# it under the terms of the GNU General Public License as published by 

# the Free Software Foundation, either version 2 of the License, or 

# (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

  

from cysignals.signals cimport sig_on, sig_off 

  

from .fmpz cimport * 

from .fmpq cimport * 

  

  

from sage.rings.integer cimport Integer 

from sage.rings.rational cimport Rational 

  

def bell_number(unsigned long n): 

""" 

Returns the `n` th Bell number. 

  

EXAMPLES:: 

  

sage: from sage.libs.flint.arith import bell_number 

sage: [bell_number(i) for i in range(10)] 

[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147] 

sage: bell_number(10) 

115975 

sage: bell_number(40) 

157450588391204931289324344702531067 

sage: bell_number(100) 

47585391276764833658790768841387207826363669686825611466616334637559114497892442622672724044217756306953557882560751 

""" 

cdef fmpz_t ans_fmpz 

cdef Integer ans = Integer(0) 

  

fmpz_init(ans_fmpz) 

  

if n > 1000: 

sig_on() 

arith_bell_number(ans_fmpz, n) 

fmpz_get_mpz(ans.value, ans_fmpz) 

fmpz_clear(ans_fmpz) 

if n > 1000: 

sig_off() 

  

return ans 

  

  

def bernoulli_number(unsigned long n): 

""" 

Return the `n`-th Bernoulli number. 

  

EXAMPLES:: 

  

sage: from sage.libs.flint.arith import bernoulli_number 

sage: [bernoulli_number(i) for i in range(10)] 

[1, -1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0] 

sage: bernoulli_number(10) 

5/66 

sage: bernoulli_number(40) 

-261082718496449122051/13530 

sage: bernoulli_number(100) 

-94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330 

""" 

cdef fmpq_t ans_fmpq 

cdef Rational ans = <Rational>Rational.__new__(Rational) 

  

fmpq_init(ans_fmpq) 

sig_on() 

arith_bernoulli_number(ans_fmpq, n) 

sig_off() 

fmpq_get_mpq(ans.value, ans_fmpq) 

fmpq_clear(ans_fmpq) 

  

return ans 

  

  

def euler_number(unsigned long n): 

""" 

Return the Euler number of index `n`. 

  

EXAMPLES:: 

  

sage: from sage.libs.flint.arith import euler_number 

sage: [euler_number(i) for i in range(8)] 

[1, 0, -1, 0, 5, 0, -61, 0] 

""" 

cdef fmpz_t ans_fmpz 

cdef Integer ans = Integer(0) 

  

fmpz_init(ans_fmpz) 

  

if n > 1000: 

sig_on() 

arith_euler_number(ans_fmpz, n) 

fmpz_get_mpz(ans.value, ans_fmpz) 

fmpz_clear(ans_fmpz) 

if n > 1000: 

sig_off() 

  

return ans 

  

  

def number_of_partitions(unsigned long n): 

""" 

Returns the number of partitions of the integer ``n``. 

  

EXAMPLES:: 

  

sage: from sage.libs.flint.arith import number_of_partitions 

sage: number_of_partitions(3) 

3 

sage: number_of_partitions(10) 

42 

sage: number_of_partitions(40) 

37338 

sage: number_of_partitions(100) 

190569292 

sage: number_of_partitions(100000) 

27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519 

  

TESTS:: 

  

sage: n = 500 + randint(0,500) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1500 + randint(0,1500) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1000000 + randint(0,1000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1000000 + randint(0,1000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1000000 + randint(0,1000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1000000 + randint(0,1000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1000000 + randint(0,1000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 1000000 + randint(0,1000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 

True 

sage: n = 100000000 + randint(0,100000000) 

sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0 # long time 

True 

""" 

cdef fmpz_t ans_fmpz 

cdef Integer ans 

  

fmpz_init(ans_fmpz) 

  

if n > 1000: 

sig_on() 

  

arith_number_of_partitions(ans_fmpz, n) 

  

if n > 1000: 

sig_off() 

  

ans = Integer(0) 

fmpz_get_mpz(ans.value, ans_fmpz) 

fmpz_clear(ans_fmpz) 

return ans 

  

def dedekind_sum(p, q): 

""" 

Return the Dedekind sum `s(p, q)` where `p` and `q` are arbitrary integers. 

  

EXAMPLES:: 

  

sage: from sage.libs.flint.arith import dedekind_sum 

sage: dedekind_sum(4, 5) 

-1/5 

""" 

p = Integer(p) 

q = Integer(q) 

s = Rational(0) 

  

cdef fmpz_t p_fmpz, q_fmpz 

cdef fmpq_t s_fmpq 

  

fmpz_init(p_fmpz) 

fmpz_init(q_fmpz) 

fmpq_init(s_fmpq) 

  

fmpz_set_mpz(p_fmpz, (<Integer>p).value) 

fmpz_set_mpz(q_fmpz, (<Integer>q).value) 

  

arith_dedekind_sum(s_fmpq, p_fmpz, q_fmpz) 

  

fmpq_get_mpq((<Rational>s).value, s_fmpq) 

  

fmpz_clear(p_fmpz) 

fmpz_clear(q_fmpz) 

fmpq_clear(s_fmpq) 

  

return s 

  

def harmonic_number(unsigned long n): 

""" 

Returns the harmonic number ``H_n``. 

  

EXAMPLES:: 

  

sage: from sage.libs.flint.arith import harmonic_number 

sage: n = 500 + randint(0,500) 

sage: bool( sum(1/k for k in range(1,n+1)) == harmonic_number(n) ) 

True 

""" 

s = Rational(0) 

cdef fmpq_t s_fmpq 

  

fmpq_init(s_fmpq) 

  

sig_on() 

arith_harmonic_number(s_fmpq, n) 

  

fmpq_get_mpq((<Rational>s).value, s_fmpq) 

sig_off() 

  

fmpq_clear(s_fmpq) 

  

return s