A208846 -id:A208846 - cp's OEIS frontend

A055775 a(n) = floor(n^n / n!).

1, 1, 2, 4, 10, 26, 64, 163, 416, 1067, 2755, 7147, 18613, 48638, 127463, 334864, 881657, 2325750, 6145596, 16263866, 43099804, 114356611, 303761260, 807692034, 2149632061, 5726042115, 15264691107, 40722913454, 108713644516

Offset: 0

Henry Bottomley, Jul 12 2000

Stirling's approximation for n! suggests that this should be about e^n/sqrt(pi*2n). Bill Gosper has noted that e^n/sqrt(pi*(2n+1/3)) is significantly better.
n^n/n! = A001142(n)/A001142(n-1), where A001142(n) is product{k=0 to n} C(n,k) (where C() is a binomial coefficient). - Leroy Quet, May 01 2004
There are n^n distinct functions from [n] to [n] or sequences on n symbols of length n, the number of those sequences having n distinct symbols is n!. So the probability P(n) of bijection is n!/n^n. The expected value of the number of functions that we pick until we found a bijection is the reciprocal of P(n), or n^n/n!. - Washington Bomfim, Mar 05 2012

			a(5)=26 since 5^5=3125, 5!=120, 3125/120=26.0416666...

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}
Eric Weisstein's World of Mathematics, Stirling's Approximation for n!

Cf. A073225, A094082, A053042, A036679, A061711, A152170, A209081, A208846, A208847.

[Floor((n^n)/Factorial(n)): n in [0..30]]; // Vincenzo Librandi, Aug 22 2011

Join[{1}, Table[Floor[n^n/n!], {n, 30}]] (* Vladimir Joseph Stephan Orlovsky, Jan 15 2009 *)

a(n)=n^n\n! \\ Charles R Greathouse IV, Apr 17 2012

a(n) = floor(A000312(n)/A000142(n)).

More terms from James Sellers, Jul 13 2000

A209833 a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.

Original entry on oeis.org

457453568161, 1362242655901, 2152302898747, 2273312197621, 4341937413061, 4777422165601, 11377272352951, 13112583010129, 23537786498641, 90022554326251, 92045875072861, 131175316104661

Offset: 1

Washington Bomfim, Mar 14 2012

Also a table "a" of the 9999 smallest strong pseudoprimes to bases 2,3,5, and 7, indexed by function f. See the expression of f in the first PARI program. The algorithm below is a fast deterministic primality test for integers x, x <= A074773(10000)-1. Note that A074773(10000)-1 > 5.6*10^18 > 2^62.
1. Run Rabin-Miller test only with base 2. If x not pass return composite.
2. Run Rabin-Miller test only with base 3. If x not pass return composite.
3. Run Rabin-Miller test only with base 5. If x not pass return composite.
4. Run Rabin-Miller test only with base 7. If x not pass return composite.
5. Compute i = f(x); if a(i) = x, return composite; otherwise return prime.
---
In first reference, p. 1022, there is a test where a table of strong pseudoprimes is used. Terms computed using data from Charles R Greathouse IV. See A074773. Third link references file "C:/temp/A.txt", a string with the first 9999 terms of A074773, each term preceded by its number of digits. Second link references file "C:/temp/V.txt", which makes the table V used by function f. It is also a string of numbers, each one preceded by its number of digits.

			a(1) = A074773(6) because f(A074773(6)) = 1. (With M = 16992, A074773(6) % 453359393 % M + 1 = 7185, and A074773(6)%450577199 % M + 1 = 7593. After running the first PARI program, one can type V[7185], and V[7593] to see that y=z = V[7185]= V[7593] = 0. So f(A074773(6)) = 1).

Washington Bomfim, C:/temp/V.txt
Washington Bomfim, C:/temp/A.txt
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
Eric Weisstein's World of Mathematics, Rabin-Miller Strong Pseudoprime Test

Cf. A208846.

s=Str(read("C:/temp/V.txt"));x=Vec(s);n=0;M=16992;i=1;V=vector(M);k=0;s="";j=0;y=0;z=0;
for(n=1,M,k=i+1;s="";for(j=1,eval(x[i]),s=concat(s,x[k]);k++);V[n]=eval(s);i=k);
\\
f(x)={y=V[x%453359393%M+1]; z=V[x%450577199%M+1]; return((y<=z)*z + (y>z)*y +1);};
\\
print("Reading file C:/temp/A.txt. Please wait...");s=Str(read("C:/temp/A.txt")); x=Vec(s);i=1;p=vector(9999);
for(n=1,9999,k=i+2;s="";for(j=1,eval(concat(x[i],x[i+1])),s=concat(s,x[k]);k++); p[n]=eval(s);i=k);
print("");a=vector(9999); for(i=1,9999,a[f(p[i])]=p[i]);for(i=1,9999, print(i," ",a[i]))

A208847 A056915(n) mod 5228905 mod 17.

Original entry on oeis.org

3, 4, 13, 15, 8, 14, 9, 5, 0, 11, 16, 10, 2, 12, 7, 1, 6, 16, 3, 10, 5, 8, 7, 16, 6, 11, 13, 6, 10, 6, 11, 16, 9, 1, 1, 15, 5, 1, 14, 7, 15, 2, 14, 9, 2, 6, 14, 3, 3, 14, 12, 6, 2, 4, 10, 16, 6, 10, 9, 3, 3, 1, 7, 9, 11, 5

Offset: 1

Washington Bomfim, Mar 02 2012

nonn

A056915(n) mod 5228905 mod 17 is a bijection from the set of the first 17 terms of A056915 to {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.
From an algorithm based on strong pseudoprimes to bases 2,3 and 5, and a table T with the first 17 terms of A056915, we can test if n is prime, odd n, 1 < n < 42550716781. When n is a prime, we check if n belongs to T. A fast way to do that is to compute i = n mod 5228905 mod 17 and compare n with T[i]. If n is not equal to T[i], n is prime.
Terms computed using table by Charles R Greathouse IV. See A056915.

Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}

Cf. A056915, A055775, A208846.

A209081 Floor(A152170(n)/n^n). Floor of the expected value of the cardinality of the image of a function from [n] to [n].

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 12, 12, 13, 14, 14, 15, 15, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 26, 26, 27, 27, 28, 29, 29, 30, 31, 31, 32, 33, 33, 34, 34, 35, 36, 36, 37, 38

Offset: 1

Washington Bomfim, Mar 05 2012

nonn

From the first commentary of A152170, a(n)= floor(A152170(n)/n^n) = floor((n(n^n-(n-1)^n))/n^n) = floor(n-(n-1)^n/n^(n-1)).

			a(1) = 1 because the image of a function from [1] to [1] has one value. a(2) = 1 since we can consider functions with domain {x,y}, and image {X,Y}. We can have f(x)=X, f(y)=X; f(x)=X, f(y)=Y; f(x)=Y, f(y)=Y; f(x)=Y, f(y)=X.
The sum of the cardinalities of the images divided by the number of functions is (1+2+1+2)/4 = 1.5. Floor(1.5)=1.

Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}

Cf. A152170.

a(n) = floor(n-(n-1)^n/n^(n-1)).

cp's OEIS Frontend

A055775 a(n) = floor(n^n / n!).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A209833 a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A208847 A056915(n) mod 5228905 mod 17.

Views

Author

Keywords

Comments

Links

Crossrefs

A209081 Floor(A152170(n)/n^n). Floor of the expected value of the cardinality of the image of a function from [n] to [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula