Alfred Heiligenbrunner - cp's OEIS frontend

User: Alfred Heiligenbrunner

Alfred Heiligenbrunner has authored 3 sequences.

A270120 Number of k with k^n=1 (mod n) and k^k=k (mod n); related to some groups of order n.

0, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 4, 1, 2, 1, 6, 1, 4, 1, 6, 3, 2, 1, 8, 5, 2, 3, 4, 1, 4, 1, 6, 1, 2, 1, 8, 1, 2, 3, 12, 1, 8, 1, 4, 3, 2, 1, 12, 7, 6, 1, 6, 1, 4, 5, 8, 3, 2, 1, 12, 1, 2, 9, 10, 1, 4, 1, 6, 1, 4, 1, 16, 1, 2, 5, 4, 1, 8, 1, 20, 9, 2, 1, 16, 1, 2, 1, 8, 1, 8, 1, 4, 3, 2, 1, 12, 1, 8, 3, 14

Offset: 1

Alfred Heiligenbrunner, Mar 11 2016

Given integers n and k, consider the operation
o_k: Z_n x Z_n -> Z_n, (a, b) -> a + k^a * b (mod n).
(Z_n, o_k) is a group if k^n == 1 (mod n) and k^k == k (mod n).
The first condition is necessary to get the definition well-defined.
The second condition is necessary for the associative property.
a(n) gives the number of different k out of {1, 2, ..., n-1} that comply the conditions.
E.g., for n = 4, k = -1 (or, what is the same, k = 3) results in the Klein four-group. (a o_3 b := a + (-1)^a * b (mod 4).)
Note that different k can result in groups that are isomorphic to each other.
The neutral element is always 0.
The inverse element to a is always -a*k^(-a) (mod n).

			a(4) = 2, because in Z_4, k == 1 and k == 3 are the only number out of {0, 1, 2, 3} with conditions k^k==k mod n and k^n==1 mod n.
a(8) = 4, because k can be out of {1, 3, 5, 7}.
a(18) = 4, because k can be out of {1, 7, 13, 17}.
If n is even, k == -1 (or, equivalently, k == n-1) is always to be counted. This group is isomorphic to the Dihedral group D_(n/2), with generating elements -1 and 2.
The following table shows the first results with n, k and the name of the group (due to A. D. Thomas and G. V. Wood: 'Group Tables', found by comparing the element-orders).
Note that for n=8, k=1 and k=5 result in Z8. None of the k results in Z2 x Z4 or in Z2 x Z2 x Z2.
Note that for n=9 all k are isomorphic to Z9, none to Z3 x Z3.
n=2, k=1: Z2
n=3, k=1: Z3
n=4, k=1: Z4
n=4, k=3: Z2 x Z2
n=5, k=1: Z5
n=6, k=1: Z6
n=6, k=5: D3
n=7, k=1: Z7
n=8, k=1: Z8
n=8, k=3: Q4
n=8, k=5: Z8
n=8, k=7: D4
n=9, k=1: Z9
n=9, k=4: Z9
n=9, k=7: Z9
n=10, k=1: Z10
n=10, k=9: D5
...

Antti Karttunen, Table of n, a(n) for n = 1..65537
Alfred Heiligenbrunner, A270120 Further examples and how the small groups were named
OEIS Wiki, OEIS Wiki Groups of order n

Cf. A000001 (number of groups of order n).

Table[Length[ Select[Range[1, n-1], ((GCD[n, # - 1] > 1) && (PowerMod[#, n, n] == 1) && (PowerMod[#, # - 1, n] == 1)) &]], {n, 1, 100}]

a(n) = sum(k=1, n-1, (Mod(k,n)^n == 1) && (Mod(k,n)^k == k)); \\ Michel Marcus, Mar 12 2016

A095808 Number of ways to write n in the form m + (m+1) + ... + (m+k-1) + (m+k) + (m+k-1) + ... + (m+1) + m with integers m>= 1, k>=1. Or, number of divisors d of 4n-1 with 0 < (d-1)^2 < 4n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 2, 0, 0, 2, 0, 0, 1, 1, 1, 2, 0, 0, 1, 1, 1, 1, 0, 0, 3, 0, 1, 2, 0, 1, 1, 0, 0, 2, 2, 0, 1, 1, 0, 3, 0, 1, 2, 0, 1, 1, 0, 0, 3, 1, 0, 2, 1, 0, 3, 1, 0, 1, 0, 2, 2, 0, 1, 1, 1, 1, 1, 0, 0, 5, 1, 1, 1, 0, 1, 1, 1, 0, 3, 1, 0, 2, 0, 1, 3, 0, 0, 2, 1, 1, 3

Offset: 1

Alfred Heiligenbrunner, Jun 15 2004

nonn

n = m + (m+1) + ... + (m+k-1) + (m+k) + (m+k-1) + ... + (m+1) + m means n = k^2 + m*(2k+1) or 4n-1 = (2k+1)*(4m+2k-1). So if 4n-1 disparts into two odd factors a*b, then k = (a-1)/2, m=(n-k^2)/(2k+1) give the solution of the origin equation. We only count solutions with k^2 < n, such that m>0. This means we are taking into account only factors a < 2n+1.

Note that a(n) = 0 if 4n-1 is prime. - Alfred Heiligenbrunner, Mar 01 2016

			a(16) = 2 because 16 = 5+6+5 and 16 = 1+2+3+4+3+2+1.
The trivial case 16=16 (k=0, m=n) is not counted. The cases m=0, e.g. 16 = 0+1+2+3+4+3+2+1+0 are not counted. The cases m<0 e.g. 16 = -4+-3+-2+-1+0+1+2+3+4+5+6+5+4+3+2+1+0+-1+-2+-3+-4 are not counted.

Alfred Heiligenbrunner, Tower-Sums of adjacent numbers (in German).

Cf. A001227, A001620, A069283, A070824, A078703.

seq((numtheory[tau](4*n-1)-2)/2, n=1..100); # Ridouane Oudra, Jan 18 2025

h1 = Table[count = 0; For[k = 1, k^2 < n, k++, If[Mod[n - k^2, 2k + 1] == 0, count++ ]]; count, {n, 100}] - or - h2 = Table[Length[Select[Divisors[4n - 1], ((# - 1)^2 < 4n) &]] - 1, {n, 100}]
a[n_] := (DivisorSigma[0, 4*n-1] - 2)/2; Array[a, 100] (* Amiram Eldar, Jan 28 2025 *)

a(n) = (numdiv(4*n-1) - 2)/2; \\ Amiram Eldar, Jan 28 2025

From Ridouane Oudra, Jan 18 2025: (Start)
a(n) = (tau(4*n-1) - 2)/2.
a(n) = A070824(4*n-1)/2.
a(n) = A078703(n) - 1. (End)
Sum_{k=1..n} a(k) = (log(n) + 2*gamma - 5 + 4*log(2))*n/4 + O(n^(1/3)*log(n)), where gamma is Euler's constant (A001620). - Amiram Eldar, Jan 27 2025

A085813 Number of cards that need to be drawn (with replacement) from a deck of n cards to have a 95% or greater chance of seeing each card at least once.

Original entry on oeis.org

1, 6, 11, 16, 21, 27, 33, 38, 44, 51, 57, 63, 70, 76, 83, 90, 96, 103, 110, 117, 124, 131, 138, 145, 152, 159, 167, 174, 181, 189, 196, 203, 211, 218, 226, 233, 241, 248, 256, 264, 271, 279, 287, 294, 302, 310, 318, 326, 333, 341, 349, 357, 365, 373, 381, 389

Offset: 1

Alfred Heiligenbrunner, Jul 25 2003

nonn

The probability that there are at most k different cards in t drawings is (k/m)^t * binomial(m,k). This also includes the cases with k-1 different cards, which we want to subtract. Inclusion and exclusion leads to the formula Sum_{k=1..m} (-1)^(m-k) * (k/m)^t * binomial(m,k).

			a(2)=6 because you have to throw a coin 6 times to get both sides at least once with probability greater than or equal to 0.95. (The probability of getting only one side in a series of 6 throws is (1/2)^6 * 2 = 1/32 = 0.03125 < 0.05.)
a(6)=27 because you have to roll a die 27 times to see all 6 possible outcomes with a probability over 0.95. (If you roll a die 27 times, the probability of getting all 6 sides at least once is 0.95658638... . If you roll the die only 26 times, the probability is 0.94798274... .)

Cf. A073593 (number of drawings for a 50% probability of seeing each card, = median) and A060293 (expected value of the number of drawings until each card is drawn once).

Cf. A090582.

f[1] = 1; f[n_] := f[n] = Block[{k = f[n - 1]}, While[ 2StirlingS2[k, n]*n!/n^k < 19/10, k++ ]; k]; Table[ f[n], {n, 1, 56}]

More terms from Robert G. Wilson v, Sep 07 2003

cp's OEIS Frontend

User: Alfred Heiligenbrunner

A270120 Number of k with k^n=1 (mod n) and k^k=k (mod n); related to some groups of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A095808 Number of ways to write n in the form m + (m+1) + ... + (m+k-1) + (m+k) + (m+k-1) + ... + (m+1) + m with integers m>= 1, k>=1. Or, number of divisors d of 4n-1 with 0 < (d-1)^2 < 4n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A085813 Number of cards that need to be drawn (with replacement) from a deck of n cards to have a 95% or greater chance of seeing each card at least once.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions