A192135 -id:A192135 - cp's OEIS frontend

A328914 Smallest index m such that from the m-th term on, the sequence {k^k mod A192135(n): k >= 0} enters into a cycle.

3, 3, 3, 3, 4, 7, 4, 7, 7, 4, 7, 11, 7, 11, 7, 11, 6, 11, 7, 15, 7, 15, 6, 15, 7, 15, 6, 19, 7, 19, 13, 6, 19, 19, 13, 8, 23, 6, 13, 23, 23, 8, 16, 11, 23, 16, 27, 11, 27, 8, 16, 27, 27, 16, 11, 8, 31, 16, 31, 11, 31, 16, 8, 31, 11, 22, 35, 35, 22, 8, 35, 16, 35, 22, 39, 8, 16, 25, 39, 39, 25, 12, 16, 39, 15, 25, 43

Offset: 1

Jianing Song, Oct 31 2019

nonn

Let f(n) be the smallest index m such that from the m-th term on, the sequence {k^k mod n: k >= 0} enters into a cycle, then:
(a) if gcd(n1,n2) = 1, then f(n1*n2) = max{f(n1), f(n2)}. For example, f(648) = max{f(8), f(81)} = 4;
(b) f(1) = 0; for primes p, f(p^e) = 1 if e <= p; f(p^e) is the largest s that is no greater than e and that s-1 is divisible by p but not by p^2.
Proof: If we define b(k) = k^k mod p^e if gcd(k,p) = 1, 0 otherwise, it is easy to see that {b(k): k >= 0} is purely periodic. As a result, for every k >= f(p^e), we have either gcd(k,p) = 1 or  p^e | k^k. In other words, let t be the largest number divisible by p such that p^e does not divide t^t, then f(p^e) = t+1.
If p^2 divides t, write t = r*p^2, then v(t^t,p) < v((t+p)^(t+p),p), where t(,p) is the p-adic valuation. This gives r = 0. As a result, f(p^e) is either 1 or a number s such that s-1 is divisible by p but not by p^2. In the latter case, v((s-1)^(s-1),p) = s-1, so s is the largest such number that is no greater than e.
The records in this sequence are {3, 4, 7, 11, 15, 19, 23, ...}

			A table for f(p^e):
              p
   e  2  3  5  7 11 13
   1  1  1  1  1  1  1
   2  1  1  1  1  1  1
   3  3  1  1  1  1  1
   4  3  4  1  1  1  1
   5  3  4  1  1  1  1
   6  3  4  6  1  1  1
   7  7  7  6  1  1  1
   8  7  7  6  8  1  1
   9  7  7  6  8  1  1
  10  7  7  6  8  1  1
  11 11  7 11  8  1  1
  12 11  7 11  8 12  1
  13 11 13 11  8 12  1
  14 11 13 11  8 12 14
  15 11 13 11 15 12 14
  16 11 16 16 15 12 14

Cf. A192135, A328920 (smallest N such that f(N) = n).

b(p,e) = if(!e, 0, if(e<=p, 1, forstep(k=e, p+1, -1, if(k%p==1&&k%(p^2)!=1, return(k)))))
L=List(); my(lim=12); forprime(p=2, lim, for(n=p+1, lim*log(lim)\log(p), listput(L, p^n))); listsort(L); L \\ generates all terms of A192135 below lim^lim
for(k=1, #L, my(p=factor(L[k])[1,1],e=factor(L[k])[1,2]); print1(b(p,e), ", "))

a(n) = f(A192135(n)), where f is defined in the comment section.

A054743 If n = Product p_i^e_i then p_i < e_i (where e_i > 0) for all i.

Original entry on oeis.org

1, 8, 16, 32, 64, 81, 128, 243, 256, 512, 648, 729, 1024, 1296, 1944, 2048, 2187, 2592, 3888, 4096, 5184, 5832, 6561, 7776, 8192, 10368, 11664, 15552, 15625, 16384, 17496, 19683, 20736, 23328, 31104, 32768, 34992, 41472, 46656

Offset: 1

James Sellers, Apr 22 2000

Closed under multiplication. Use A104126 to construct A192135 by putting A104126(n) * prime(n)^k in a list up to some chosen bound. Create this sequence by multiplying any k elements of A192135 with distinct prime factors in a list (k>1). The last list along with A192135 is this sequence when sorted. - David A. Corneth, Jun 07 2016

			8 appears in the list because 8 = 2^3 and 2<3.
Construction of elements up to 1000: 1. Put 2^3 and 3^5 in a list; {8, 81} (The terms of A104126 up to 1000.) 2. For each element, put products the last list with their distinct prime factors up to 1000. Gives: {8, 16, 32, 64, 128, 256, 512, 81, 243, 729} (Terms from A192135 up to 1000). 3. Put products of k powers of distinct primes in a new list up to 1000: {648} (k>1). Unite {648} with {8, 16, 32, 64, 128, 256, 512, 81, 243, 729}. {8, 16, 32, 64, 128, 256, 512, 81, 243, 729, 648}. Sort the list. This gives: {8, 16, 32, 64, 81, 128, 243, 256, 512, 648, 729}, which are the elements below 1000 in this sequence. - _David A. Corneth_, Jun 07 2016

Robert Israel, Table of n, a(n) for n = 1..10001

Cf. A048103, A054744, A104126, A192135.

Cf. A207481 (same construction, but with p_i>=e_i),

N:= 10^10: # to get all terms <= N
p:= 1:
S:= {1}:
do
  p:= nextprime(p);
  if p^(p+1) > N then break fi;
  pp:= [seq(p^j, j=p+1 .. ilog[p](N))];
  S:= S union select(`<=`,{seq(seq(s*q,s=S),q=pp)},N);
od:
sort(convert(S,list)); # Robert Israel, Jun 07 2016

okQ[n_] := AllTrue[FactorInteger[n], #[[1]] < #[[2]]&];
Join[{1}, Select[Range[50000], okQ]] (* Jean-François Alcover, Jun 08 2016 *)

lista(nn) = {for (n=1, nn, f = factor(n); ok = 1; for (i=1, #f~, if (f[i, 1] >= f[i, 2], ok = 0; break;);); if (ok, print1(n, ", ")););} \\ Michel Marcus, Jun 15 2013

Sum_{n>=1} 1/a(n) = Product_{p prime} 1 + 1/((p-1)*p^p) = 1.27325025767774256043... - Amiram Eldar, Nov 24 2020

1 prepended by Alec Jones, Jun 07 2016

A074583 Numbers k such that sopfr(k) = S(k), where sopfr = A001414 and S = A002034.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239

Offset: 1

Jason Earls, Aug 24 2002

These are the prime powers p^e with e <= p. - Reinhard Zumkeller, Dec 15 2003

Complement to A192135 with respect to A000961;

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Subsequence of A000961; A000040, A000430, and A051674 are subsequences.

Cf. A095874, A192135, A192188, A343983.

import Data.Set (singleton, deleteFindMin, insert)
a074583 n = a074583_list !! (n-1)
a074583_list = 1 : f (singleton 2) a000040_list where
  f s ps'@(p:p':ps)
    | m == p      = p : f (insert (p*p) $ insert p' s') (p':ps)
    | m < spf^spf = m : f (insert (m*spf) s') ps'
    | otherwise   = m : f s' ps'
      where spf = a020639 m  -- smallest prime factor of m, cf. A020639
            (m, s') = deleteFindMin s
-- Simpler version:
a074583_list = map a000961 a192188_list
-- Reinhard Zumkeller, Jun 05 2011, Jun 26 2011

sopfr[n_] := Total[Times @@@ FactorInteger[n]];
S[n_] := Module[{m = 1}, While[!IntegerQ[m!/n], m++]; m];
Select[Range[1000], sopfr[#] == S[#]&] (* Jean-François Alcover, Nov 09 2017 *)

isok(n) = my(f=factor(n)); n==1 || (#f~==1 && f[1, 1]>=f[1, 2]); \\ Seiichi Manyama, May 07 2021

a(n) = A000961(A192188(n)); A095874(a(n)) = A192188(n). - Reinhard Zumkeller, Jun 26 2011

A257278 Prime powers p^m with p <= m.

Original entry on oeis.org

4, 8, 16, 27, 32, 64, 81, 128, 243, 256, 512, 729, 1024, 2048, 2187, 3125, 4096, 6561, 8192, 15625, 16384, 19683, 32768, 59049, 65536, 78125, 131072, 177147, 262144, 390625, 524288, 531441, 823543, 1048576, 1594323, 1953125, 2097152, 4194304, 4782969, 5764801, 8388608, 9765625

Offset: 1

M. F. Hasler, Apr 28 2015

nonn

Might be called "high" powers of primes. Motivated by challenges for which low powers of large primes provide somewhat trivial solutions, cf. A257279. The definition also avoids the question of the whether prime itself is to be considered as a prime power or not, cf. A000961 vs. A025475. In view of the condition p <= n, up to 10^10, only powers of the primes 2, 3, 5 and 7 (namely, less than 10) can occur.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000961, A025475, A257279.
Cf. A000040, A051674 (subsequence).
Subsequence of A122494 and A192135 (p < m, subsequence).
Cf. A257572, A257573.

import Data.Set (singleton, deleteFindMin, insert)
a257278 n = a257278_list !! (n-1)
a257278_list = f (singleton (4, 2)) 27 (tail a000040_list) where
   f s pp ps@(p:ps'@(p':_))
     | qq > pp   = pp : f (insert (pp * p, p) s) (p' ^ p') ps'
     | otherwise = qq : f (insert (qq * q, q) s') pp ps
     where ((qq, q), s') = deleteFindMin s
-- Reinhard Zumkeller, May 01 2015

seq[lim_] := Module[{s = {}, p = 2}, While[p^p <= lim, AppendTo[s, p^Range[p, Log[p, lim]]]; p = NextPrime[p]]; Sort[Flatten[s]]]; seq[10^7] (* Amiram Eldar, Apr 14 2025 *)

L=List();lim=10;forprime(p=1,lim,for(n=p,lim*log(lim)\log(p),listput(L,p^n)));listsort(L);L

a(n) = A257572(n) ^ A257573(n). - Reinhard Zumkeller, May 01 2015

Sum_{n>=1} 1/a(n) = Sum_{p prime} 1/(p^(p-1)*(p-1)) = 0.55595697220270661763... - Amiram Eldar, Oct 24 2020

A192187 Positions of prime powers p^e with p < e within A000961.

Original entry on oeis.org

7, 11, 19, 28, 33, 45, 69, 71, 118, 153, 199, 341, 360, 605, 894, 1079, 1881, 1962, 2294, 3591, 6060, 6636, 7772, 12371, 16229, 23151, 33292, 43580, 44126, 82268, 121021, 146014, 155922, 296348, 334771, 398221, 564689, 650688, 931905, 1078556, 2064590, 2454882

Offset: 1

Reinhard Zumkeller, Jun 26 2011

nonn

Complement of A192188.
A000961(a(n)) = A192135(n).
a(n) = A095874(A192135(n)).

a(22)-a(42) from Donovan Johnson, Jul 09 2011

cp's OEIS Frontend

A328914 Smallest index m such that from the m-th term on, the sequence {k^k mod A192135(n): k >= 0} enters into a cycle.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A054743 If n = Product p_i^e_i then p_i < e_i (where e_i > 0) for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A074583 Numbers k such that sopfr(k) = S(k), where sopfr = A001414 and S = A002034.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A257278 Prime powers p^m with p <= m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A192187 Positions of prime powers p^e with p < e within A000961.

Views

Author

Keywords

Formula

Extensions