Experiment
In this note we study the function eumija(a, b) = eu(a, b) - ja(a, b).
eu(a, b) counts the number of modulo operations in the Euclidean Algorithm when computing the Greatest common divisor of a and b. ja(a, b) counts the number of modulo operations in the calculation of the Jacobi Symbol of a and b. Note that ja(a, b) in the below code will also be defined when b is even.
In Kotlin we write
fun eu(A: Int, B: Int): Int {
var a = A
var b = B
var c = 0
while (b != 0) {
a = b.also { b = a % b }
c++
}
return c
}
fun ja(A: Int, B: Int): Int {
var a = A
var b = B
var c = 0
while (b != 0) {
while (b and 1 == 0)
b = b shr 1
a = b.also { b = a % b }
c++
}
return c
}
fun eumija(a: Int, b: Int) = eu(a, b) - ja(a, b)
fun main(args: Array<String>) {
val m = if (args.isNotEmpty()) args[0].toIntOrNull() ?: 9 else 9
for (a in 0..m) {
print("$a: ")
for (b in 0..m)
print("${eumija(a, b)} ")
println()
}
println()
var c = 0
for (n in 1..if (args.count() >= 2)
args[1].toIntOrNull() ?: 1024 else 1024) {
val r = eumija(n-1, n)
if (r > 0) {
print("$n:$r ")
if (++c % 10 == 0)
println()
}
}
}
Running this program with the arguments "9 1024" yields
0: 0 0 0 0 0 0 0 0 0 0
1: 0 0 1 0 1 0 0 0 1 0
2: 0 0 0 1 1 1 0 1 1 1
3: 0 0 1 0 2 1 1 0 3 0
4: 0 0 0 0 0 1 1 2 1 1
5: 0 0 1 1 1 0 1 1 4 1
6: 0 0 0 0 1 0 0 0 2 1
7: 0 0 1 0 2 1 0 0 2 1
8: 0 0 0 1 0 1 0 0 0 1
9: 0 0 1 0 1 1 1 1 1 0
2:1 3:1 4:2 5:1 6:1 8:2 9:1 10:1 12:1 16:2
17:1 18:1 20:1 24:1 32:2 33:1 34:1 36:1 40:1 48:1
64:2 65:1 66:1 68:1 72:1 80:1 96:1 128:2 129:1 130:1
132:1 136:1 144:1 160:1 192:1 256:2 257:1 258:1 260:1 264:1
272:1 288:1 320:1 384:1 512:2 513:1 514:1 516:1 520:1 528:1
544:1 576:1 640:1 768:1 1024:2
It appears that the values for n where eumija(n - 1, n) is positive are the values of this sequence: Integers with one or two 1-bits in their binary expansion.
Disclaimer
Please note that the Kotlin code on this page is copyrighted by Peter Schorn and may not be reproduced or stored on any computer system without the written permission of Peter Schorn. In particular you are not allowed to use this code or page or parts of it for any machine learning or similar purposes. You can write an email to Peter Schorn and ask for permission.