John Metcalf - cp's OEIS frontend

User: John Metcalf

John Metcalf has authored 2 sequences.

A365262 Numbers k which never require the maximum number of steps for the Euclidean algorithm to compute gcd(k,m) for any m > k.

54, 78, 96, 135, 150, 156, 164, 182, 252, 304, 336, 442, 480, 483, 525, 532, 558, 570, 582, 640, 645, 675, 740, 744, 780, 912, 918, 922, 924, 1012, 1046, 1132, 1155, 1164, 1170, 1206, 1218, 1320, 1422, 1424, 1450, 1452, 1456, 1488, 1496, 1536, 1548, 1568, 1594

Offset: 1

John Metcalf, Aug 29 2023

nonn

			k = 54 is a term as the number of steps required to compute the Euclidean algorithm gcd(k, m) is smaller than A034883(m) for all m > k.
k = 27 is not a term as the number of steps required to compute the Euclidean algorithm gcd(k, m) is equal to A034883(m) for m = 35 (steps = 5), 44 (steps = 6) and 46 (steps = 6).

Cf. A034883, A051010, A364405.

def gcdsteps(k, m)
  k.zero? ? 0 : 1 + gcdsteps(m % k, k)
end
flags = [nil, *1..5000]
(1..flags.length).each do |m|
  scores = []
  (1..m).each do |k|
    scores << [gcdsteps(k, m), k]
  end
  scores.sort_by! { |n| n[0] }
  scores.select { |n| n[0] == scores.last[0] }.each do |n|
    flags[n[1]] = nil
  end
end
print flags[1..flags.length / 2].compact

A364405 Numbers k such that k is never the smallest number which requires the maximum number of steps for the Euclidean algorithm for computing gcd(k,m) for any m > k.

Original entry on oeis.org

12, 16, 20, 24, 38, 46, 48, 50, 54, 56, 66, 70, 78, 81, 84, 88, 91, 96, 98, 99, 100, 104, 116, 122, 126, 130, 132, 135, 138, 141, 148, 150, 155, 156, 161, 162, 164, 166, 168, 176, 180, 182, 193, 196, 200, 201, 204, 205, 210, 212, 214, 218, 220, 228, 232, 234, 236

Offset: 1

John Metcalf, Jul 22 2023

nonn

Positive numbers not in A084242.

Cf. A084242, A051010.

def gcdsteps(k, m)
  k.zero? ? 0 : 1 + gcdsteps(m % k, k)
end
flags = [nil, *1..2000]
(1..flags.length).each do |m|
  scores = []
  (1..m).each do |k|
    scores << [gcdsteps(k, m), k]
  end
  flags[scores.sort_by { |n| -n[0] }.first[1]] = nil
end
puts flags[1..flags.length / 2].compact

cp's OEIS Frontend

User: John Metcalf

A365262 Numbers k which never require the maximum number of steps for the Euclidean algorithm to compute gcd(k,m) for any m > k.

Views

Author

Keywords

Examples

Crossrefs

Programs

Ruby