A076497 -id:A076497 - cp's OEIS frontend

A179239 Permutation classes of integers, each identified by its smallest member.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 39, 40, 44, 45, 46, 47, 48, 49, 50, 55, 56, 57, 58, 59, 60, 66, 67, 68, 69, 70, 77, 78, 79, 80, 88, 89, 90, 99, 100, 101, 102, 103

Offset: 0

Aaron Dunigan AtLee, Jul 04 2010

Let the "permutation set" of a positive integer n be the set of all integers formed by permuting the digits of n. Two integers are "permutationally congruent" if they generate the same permutation set. A "permutation class" is a set of all permutationally congruent integers. This sequence lists each permutation class, identified by its smallest member.
These are also the positive integers in order, omitting any d-digit number n if a previously listed d-digit number is a permutation of the digits of n.
Range of A328447: smallest representative of the equivalence class of all numbers having the same digits up to permutation. Equivalently: Numbers with digits in nondecreasing order, except that the smallest nonzero digit must precede the zero digits. This sequence is useful when considering functions which depend only on the digits of n, e.g., the number of primes contained in n, cf. A039993, A039999, A075053 and the records therein, A072857 (primeval numbers) and A076497, resp. A239196 and A239197, etc. - M. F. Hasler, Oct 18 2019

			The permutation set of 24 is {24, 42}, and this is the equivalence class modulo permutations of both of them, so 24 is listed, but 42 is not.
The permutation set of 30 is {3, 30}, but 3 is not in the same permutation class as 30 since 30 cannot be obtained by permuting digits of 3. Therefore 30 is listed separately from 3.
The numbers 89 and 98 are also permutationally congruent and form a permutation class, so only the smaller one is listed.

Aaron Dunigan AtLee and Michael De Vlieger, Table of n, a(n) for n = 0..10000 (first 2997 terms from Aaron Dunigan AtLee; prefix 0 by _Georg Fischer_, Oct 24 2019)

A variant of A009994.
Cf. A047726, A035927 (Number of distinct n-digit numbers up to permutations of digits).
Cf. A004186, A328447: largest & smallest representative of the class of n.

maxTerm = 103; (*maxTerm is the greatest term you wish to see*) permutationSet[n_Integer] := FromDigits /@ Permutations[IntegerDigits[n]]; permutationCongruentQ[x_Integer, y_Integer] := Sort[permutationSet[x]] == Sort[permutationSet[y]]; DeleteDuplicates[Range[maxTerm], permutationCongruentQ]
f[n_] := Block[{a = {0}, b = {DigitCount[0]}, i, w}, Do[w = DigitCount@ i; AppendTo[b, w]; If[! MemberQ[Most@ b, w], AppendTo[a, i]], {i, n}]; Rest@ a]; f@ 103 (* or faster: *)
Select[Range@ 103, LessEqual @@ IntegerDigits@ # || And[Take[IntegerDigits@ #, Last@ DigitCount@ # + 1] == Reverse@ Take[Sort@ IntegerDigits@ #, Last@ DigitCount@ # + 1], LessEqual @@ DeleteCases[IntegerDigits@ #, d_ /; d == 0]] &] (* Michael De Vlieger, Jul 14 2015 *)

is(n) = {my(d=digits(n),i); for(i=2,#d, if(d[i]!=0, d=vecextract(d,concat([1],vector(#d-i+1,j,i-1+j))); break));d==vecsort(d)||n/10^valuation(n,10)<10}
\\given an element n, in base b, find the next element from the sequence.
nxt(n,{b=10}) = {my(d = digits(n)); i = #d; while(i>0&&d[i]==b-1,i--); if(i>1, if(d[i]>0, d[i]++, d[i]=d[1];);for(j=i+1,#d,d[j]=d[i]), if(i==1, d[i]++;for(j=2,#d,d[j]=0), return(10^(#d))));sum(j=1,#d,d[j]*10^(#d-j))} \\ David A. Corneth, Apr 23 2016

select( is_A179239(n)={n==A328447(n)}, [0..200]) \\ M. F. Hasler, Oct 18 2019

from itertools import count, chain, islice
from sympy.utilities.iterables import combinations_with_replacement
def A179239_gen(): # generator of terms
    return chain((0,),(int(a+''.join(b)) for l in count(1) for a in '123456789' for b in combinations_with_replacement('0'+''.join(str(d) for d in range(int(a),10)),l-1)))
A179239_list = list(islice(A179239_gen(),31)) # Chai Wah Wu, Sep 13 2022

Prefixed with a(0) = 0 by M. F. Hasler, Oct 18 2019

A039993 Number of different primes embedded in n.

Original entry on oeis.org

0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 3, 1, 1, 1, 3, 0, 1, 1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 3, 1, 2, 3, 1, 4, 2, 1, 0, 1, 1, 2, 0, 1, 0, 2, 0, 0, 1, 1, 2, 3, 1, 1, 1, 2, 1, 2, 0, 1, 1, 1, 0, 1, 0, 2, 0, 0, 1, 3, 2, 4, 2, 2, 2, 1, 1, 3, 0, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 2, 0, 3, 1, 0, 0, 2, 1, 4, 2, 1

Offset: 1

David W. Wilson

a(n) counts (distinct) permuted subsequences of digits of n which denote primes.

			a(17) = 3 since we can obtain 7, 17 and 71. a(22) = 1, since we can get only one prime (in contrast, A075053(22) = 2).
a(1013) = 14 because the prime subsets derived from the digital permutations of 1013 are {3, 11, 13, 31, 101, 103, 113, 131, 311, 1013, 1031, 1103, 1301, 3011}.

T. D. Noe, Table of n, a(n) for n=1..10000
C. K. Caldwell, The Prime Glossary, Primeval Number
J. P. Delahaye, Primes Hunters, 1379 is very primeval (in French)
Mike Keith, Integers containing many embedded primes
W. Schneider, Primeval Numbers
G. Villemin's Almanach of Numbers, Mike Keith's Primeval Number (in French).

Different from A075053. For records see A072857, A076497. See also A134596, A134597.

Cf. A039999.

Needs["DiscreteMath`Combinatorica`"]; f[n_] := Block[{a = Drop[ Sort[ Subsets[ IntegerDigits[n]]], 1], b = c = {}, k = 1, l}, l = Length[a] + 1; While[k < l, b = Append[b, Permutations[ a[[k]] ]]; k++ ]; b = Union[ Flatten[b, 1]]; l = Length[b] + 1; k = 1; While[k < l, c = Append[c, FromDigits[ b[[k]] ]]; k++ ]; Count[ PrimeQ[ Union[c]], True]]; Table[ f[n], {n, 1, 105}]
Table[Count[Union[FromDigits/@(Flatten[Permutations/@Subsets[ IntegerDigits[ n]],1])],?PrimeQ],{n,110}] (* _Harvey P. Dale, Nov 29 2017 *)

A039993(n)={my(S=[],D=vecsort(digits(n))); for(i=1,2^#D-1, forperm(vecextract(D,i),p, isprime(fromdigits(Vec(p)))||next; S=setunion(S,[fromdigits(Vec(p))]))); #S} \\ To avoid duplicate scan of identical subsets of digits, one could skip the corresponding range of indices i when a binary pattern ...10... is detected. - M. F. Hasler, Mar 08 2014, simplified Oct 15 2019

from itertools import permutations
from sympy import isprime
def a(n):
    l=list(str(n))
    L=[]
    for i in range(len(l)):
        L+=[int("".join(x)) for x in permutations(l, i + 1)]
    return len([i for i in set(L) if isprime(i)])
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 25 2017

from sympy.utilities.iterables import multiset_permutations
from sympy import isprime
def A039993(n): return sum(1 for l in range(1,len(str(n))+1) for a in multiset_permutations(str(n),size=l) if a[0] !='0' and isprime(int(''.join(a)))) # Chai Wah Wu, Sep 13 2022

Edited by Robert G. Wilson v, Nov 25 2002

Keith link repaired by Charles R Greathouse IV, Aug 13 2009

A072857 Primeval numbers: numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits.

Original entry on oeis.org

1, 2, 13, 37, 107, 113, 137, 1013, 1037, 1079, 1237, 1367, 1379, 10079, 10123, 10136, 10139, 10237, 10279, 10367, 10379, 12379, 13679, 100279, 100379, 101237, 102347, 102379, 103679, 123479, 1001237, 1002347, 1002379, 1003679, 1012349, 1012379, 1023457, 1023467, 1023479, 1234579, 1234679, 10012349

Offset: 1

Lekraj Beedassy, Jul 26 2002

RECORDS transform of A039993. - N. J. A. Sloane, Jan 25 2008. See A239196 and A239197 for the RECORDS transform of the closely related sequence A075053. - M. F. Hasler, Mar 12 2014
"73 is the largest integer with the property that all permutations of all of its substrings are primes." - M. Keith
Smallest monotonic increasing subsequence of A076449. - Lekraj Beedassy, Sep 23 2006
From M. F. Hasler, Oct 15 2019: (Start)
All terms > 37 start with leading digit 1 and have all other digits in nondecreasing order. The terms are smallest representatives of the class of numbers having the same digits, cf. A179239 and A328447 which both contain this as a subsequence.
The frequency of primes is roughly 50% for the displayed values, but appears to decrease. Can it be proved that the asymptotic density is zero?
Can we prove that there are infinitely many even terms? (Of the form 10...01..12345678?)
Can it be proved that there is no term that is a multiple of 3? (Or the contrary? Are there infinitely many?) (End)

			1379 is in the sequence because it is the smallest number whose digital permutations form a total of 31 primes, viz. 3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97, 137, 139, 173, 179, 193, 197, 317, 379, 397, 719, 739, 937, 971, 1973, 3719, 3917, 7193, 9137, 9173, 9371.

J.-P. Delahaye, Merveilleux nombres premiers ("Amazing primes"), "1379's quite primeval, is it not?", pp. 318-321, Pour la Science, Paris 2000.

Giovanni Resta, Table of n, a(n) for n = 1..100
C. K. Caldwell, The Prime Glossary, primeval number
J. P. Delahaye, Primes Hunters, 1379 is very primeval (in French)
M. Keith, Integers containing many embedded primes
W. Schneider, Primeval Numbers
N. J. A. Sloane, Transforms
G. Villemin's Almanach of Numbers, Nombre Primeval de Mike Keith
Wikipedia, Primeval number

Cf. A039993, A075053, A076497, A239196, A239197.
A076449 gives a similar sequence.
Cf. A119535 (prime subsequence).

(*first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) f[n_] := Length[ Select[ FromDigits /@ Flatten[ Permutations /@ Subsets[ IntegerDigits[ n]], 1], PrimeQ[ # ] &]]; d = -1; Do[ b = f[n]; If[b > d, Print[n]; d = b], {n, 2^20}] (* Robert G. Wilson v, Feb 12 2005 *)
Join[{1},DeleteDuplicates[Table[{n,Count[Union[FromDigits/@Flatten[Permutations[#]&/@Subsets[IntegerDigits[n]],1]],?PrimeQ]},{n,2,125000}],GreaterEqual[#1[[2]],#2[[2]]]&][[;;,1]]] (* The program generates the first 30 terms of the sequence. *) (* _Harvey P. Dale, Nov 16 2024 *)

A072857_upto(num_digits,s=1,m=-1,L=List())={for(n=s,num_digits, my(u=10^(n-1)); forvec(v=vector(n-(n>2),i,[0,if(n>6,9*(i+1)\n,n>3,10-(n-i)\.6,7)]), m<A039993(u+fromdigits(v)) && m=A039993(listput(L,u+fromdigits(v))),1)); Vec(L)} \\ Optional 2nd and 3rd arg allow to extend a previous computation. - M. F. Hasler, Oct 15 2019

Python
```
# see linked program in A076449
```

Edited, corrected and extended by Robert G. Wilson v, Nov 12 2002

Comment corrected by N. J. A. Sloane, Jan 25 2008

A076730 Maximum number of (distinct) primes that an n-digit number may shelter (i.e., primes contained among all digital substrings' permutations).

Original entry on oeis.org

1, 4, 11, 31, 106, 402, 1953, 10542, 64905, 362451, 2970505

Offset: 1

Lekraj Beedassy, Nov 08 2002

See sequence A134596 for the least numbers of given length which yields these maxima over n-digit indices for A039993. - M. F. Hasler, Mar 11 2014

By definition this is a subsequence of A076497. The term a(10) was incorrectly given as 398100 = A075053(1123456789), which double-counts each prime using only one digit '1'. But a(10) = A039993(1123456789) = A076497(80) = 362451. The values given for a(9) and a(11) were also incorrect, the latter probably for the same reason, and for a(9) probably due to double-counting of primes with leading zeros. - M. F. Hasler and David A. Corneth, Oct 15 2019

			We have a(3)=11, since among numbers 100 through 999, the smallest ones having 5, 6, 7, 8, 10, 11 embedded primes are respectively 107, 127, 113, 167, 179, 137 (the last of these being the first reaching the maximum number of 11 embedded primes, viz. 3, 7, 13, 17, 31, 37, 71, 73, 137, 173, 317).

M. Keith, Integers containing many embedded primes
W. Schneider, MATHEWS, Primeval Numbers

Cf. A072857, A076449, A076497, A134596 (largest n-digit primeval number).

Cf. A075053 (a variant of A039993), A134597 (= max A075053(1..10^n-1)).

a(n,m=0)=for(k=10^(n-1),10^n-1,A039993(k)>m&&m=A039993(k));m \\ M. F. Hasler, Mar 09 2014

Python
```
# see linked program in A076449
```

a(n) = A039993(A134596(n)) = max { A039993(m); m in A072857 and m < 10^n }. - M. F. Hasler, Mar 12 2014

a(n) = A076497(k) for k such that A072857(k) = A134596(n). - M. F. Hasler, Oct 15 2019

Link fixed by Charles R Greathouse IV, Aug 13 2009
a(6) from M. F. Hasler, Mar 09 2014
a(7)-a(11) from Robert G. Wilson v, Mar 11 2014
a(9)-a(11) corrected by M. F. Hasler, Oct 15 2019

A239197 The record values A075053 associated to the records (indices) listed in A239196.

Original entry on oeis.org

0, 1, 3, 4, 5, 9, 11, 17, 19, 21, 23, 25, 26, 29, 31, 32, 33, 44, 48, 52, 66, 89, 96, 106, 117, 164, 211, 236, 248, 311, 349

Offset: 1

M. F. Hasler, Mar 12 2014

This and A239196 are the analogs (related to A075053) of A076497 and A072857 (primeval numbers), related to A039993.

m=-1; for(k=1, 9e9, A075053(k)>m&&print1(m=A075053(k),",")) \\ Not very efficient; from 199, 1999, 19999 etc one can jump to the next larger power of 10. - M. F. Hasler, Mar 12 2014

a(n)=A075053(A239196(n)).

A173052 Partial sums of A072857.

Original entry on oeis.org

1, 3, 16, 53, 160, 273, 410, 1423, 2460, 3539, 4776, 6143, 7522, 17601, 27724, 37860, 47999, 58236, 68515, 78882, 89261, 101640, 115319, 215598, 315977, 417214, 519561, 621940, 725619, 849098, 1850335, 2852682, 3855061, 4858740, 5871089

Offset: 1

Jonathan Vos Post, Feb 08 2010

Partial sums of primeval numbers. Primeval number: a prime which "contains" more primes in it than any preceding number. Here "contains" means may be constructed from a subset of its digits. E.g., 1379 contains 3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97, 137, 139, 173, 179, 193, 197, 317, 379, 397, 719, 739, 937, 971, 1973, 3719, 3917, 7193, 9137, 9173 and 9371. The subsequence of prime partial sums of primeval numbers begins: 3, 53, 1423, 3539, 6143, 89261, 115319, 315977. What is the smallest primeval prime partial sums of primeval numbers, i.e. the intersection of this sequence with A119535?

			a(36) = 1 + 2 + 13 + 37 + 107 + 113 + 137 + 1013 + 1037 + 1079 + 1237 + 1367 + 1379 + 10079 + 10123 + 10136 + 10139 + 10237 + 10279 + 10367 + 10379 + 12379 + 13679 + 100279 + 100379 + 101237 + 102347 + 102379 + 103679 + 123479 + 1001237 + 1002347 + 1002379 + 1003679 + 1012349 + 1012379.

Chris K. Caldwell AND G. L. Honaker, Jr., A BRIEF PRIME CURIOS! GLOSSARY.

Cf. A000040, A072857, A039993, A075053, A076497, A076449, A119535 (prime subsequence).

a(n) = SUM[i=1..n] A072857(i) = SUM[i=1..n] {numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits}.

cp's OEIS Frontend

A088130 Erroneous version of A076497.

Views

Author

Keywords

A179239 Permutation classes of integers, each identified by its smallest member.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Extensions

A039993 Number of different primes embedded in n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Extensions

A072857 Primeval numbers: numbers that set a record for the number of distinct primes that can be obtained by permuting some subset of their digits.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A076730 Maximum number of (distinct) primes that an n-digit number may shelter (i.e., primes contained among all digital substrings' permutations).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A239197 The record values A075053 associated to the records (indices) listed in A239196.

Views

Author

Keywords

Comments

Programs

PARI

Formula

A173052 Partial sums of A072857.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula