cp's OEIS Frontend

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

%I A365262 #15 Sep 30 2023 21:38:55
%S A365262 54,78,96,135,150,156,164,182,252,304,336,442,480,483,525,532,558,570,
%T A365262 582,640,645,675,740,744,780,912,918,922,924,1012,1046,1132,1155,1164,
%U A365262 1170,1206,1218,1320,1422,1424,1450,1452,1456,1488,1496,1536,1548,1568,1594
%N A365262 Numbers k which never require the maximum number of steps for the Euclidean algorithm to compute gcd(k,m) for any m > k.
%e A365262 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.
%e A365262 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).
%o A365262 (Ruby)
%o A365262 def gcdsteps(k, m)
%o A365262   k.zero? ? 0 : 1 + gcdsteps(m % k, k)
%o A365262 end
%o A365262 flags = [nil, *1..5000]
%o A365262 (1..flags.length).each do |m|
%o A365262   scores = []
%o A365262   (1..m).each do |k|
%o A365262     scores << [gcdsteps(k, m), k]
%o A365262   end
%o A365262   scores.sort_by! { |n| n[0] }
%o A365262   scores.select { |n| n[0] == scores.last[0] }.each do |n|
%o A365262     flags[n[1]] = nil
%o A365262   end
%o A365262 end
%o A365262 print flags[1..flags.length / 2].compact
%Y A365262 Cf. A034883, A051010, A364405.
%K A365262 nonn
%O A365262 1,1
%A A365262 _John Metcalf_, Aug 29 2023