login
Number of mappings f:{1,2,3,...,n} -> {1,2,3,...,n} such that gcd(f(x),f(y)) = f(gcd(x,y)) for all x,y in {1,2,3,...,n}.
2

%I #15 Aug 13 2015 08:24:19

%S 1,3,9,26,106,191,954,2427,8404,15945,111952,141117,1176623,2270566,

%T 4477947,10345290,104257447,145407966,1633452518,2517488363,

%U 5024167821,9148333241,120260250853

%N Number of mappings f:{1,2,3,...,n} -> {1,2,3,...,n} such that gcd(f(x),f(y)) = f(gcd(x,y)) for all x,y in {1,2,3,...,n}.

%C The greatest common divisor condition was suggested by A061446.

%H Manfred Scheucher, <a href="/A126025/a126025.sage.txt">Sage Script</a>

%H Manfred Scheucher, <a href="/A126025/a126025.c.txt">C Code</a>

%o (Haskell)

%o a126025 n = h n1s 0 where

%o h us c = if us == nns then c + 1 else h (succ us) (c + g) where

%o g = if and [f x `gcd` f y == f (x `gcd` y) |

%o x <- [1 .. n - 1], y <- [x + 1 .. n]] then 1 else 0

%o f = (us !!) . subtract 1

%o succ (z:zs) = if z < n then (z + 1) : zs else 1 : succ zs

%o n1s = take n [1, 1 ..]; nns = take n [n, n ..]

%o -- _Reinhard Zumkeller_, May 04 2014

%Y Cf. A061446.

%Y Cf. A000312.

%K nonn,more,nice

%O 1,2

%A _John W. Layman_, Feb 27 2007

%E a(10)-a(22) from _Manfred Scheucher_, Jun 06 2015

%E a(23) from _Manfred Scheucher_, Aug 13 2015