Jim Nastos - cp's OEIS frontend

A385156 The number of undirected, simple, unlabeled graphs G on n vertices which are prime, not split, and do not contain a vertex of degree 1 in G or in the complement of G, and has no induced P5 in G or in the complement of G.

0, 0, 0, 0, 1, 0, 0, 0, 0, 22, 310, 4177

Offset: 1

Jim Nastos and Clara Elliott, Jul 22 2025

Here, "prime" means with respect to modular decomposition (see link). A P5 is a path on 5 vertices. A split graph is a graph whose vertices can be partitioned into a clique and an independent set. Related to conjectures in the referenced paper.

			a(5) = 1 is the C5.
One of the examples of a(10) = 22 is available in the links.

Maria Chudnovsky and Peter Maceli, "Simplicial Vertices in Graphs with no Induced Four-Edge Path or Four-Edge Antipath, and the H6-Conjecture," Journal of Graph Theory, vol 76, no 4, (2014).

Maria Chudnovsky and Peter Maceli, Simplicial Vertices in Graphs with no Induced Four-Edge Path or Four-Edge Antipath, and the H6-Conjecture, arXiv:1302.0404 [math.CO], 2013.
House of Graphs, One of the 22 graphs on 10 vertices.
Sean A. Irvine, Java program (github)
Wikipedia, Modular decomposition.

Cf. A385697 (when split graph condition is dropped).

a(11)-a(12) from Sean A. Irvine, Aug 17 2025

A385929 Number of simple, undirected, prime graphs G on n unlabeled vertices with no degree-1 vertex in G or its complement, as well as having no induced P5 in G or in its complement.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 1, 9, 142

Offset: 1

Jim Nastos and Clara Elliott, Jul 12 2025

Here, "prime" means with respect to modular decomposition (see link). A P5 is a path on 5 vertices.

			The only such graph on n=5 is the C5. The only such graph on n=8 is the split graph called the 4-sun (see the House of Graphs link).

The House of Graphs, 4-sun graph
Wikipedia, Modular decomposition.

Cf. A079473, A385693, A385697.

A385693 Number of prime graphs, G, on n vertices which do not contain a degree-1 vertex in G nor in co-G.

Original entry on oeis.org

0, 0, 0, 0, 1, 6, 76, 1990, 84040, 5749698

Offset: 1

Jim Nastos and Clara Elliott, Jul 07 2025

Here, "prime" means with respect to modular decomposition (see link).

			The smallest such graph is the cycle on 5 vertices. The 6 graphs on 6 vertices are the C6, domino, X37 (as named on GraphClasses) and their three respective complements.

GraphClasses, List of Small Graphs.
Wikipedia, Modular decomposition.

Cf. A079473.

for n in range(3, 11):
    count = 0
    for g in graphs.nauty_geng(f"{n} -c -d2"):
        degrees = g.degree()
        if max(degrees) < n-2 and g.is_prime():
            count += 1
    print(f"n = {n}: {count} prime graphs")

A385697 Number of unlabeled simple graphs on n vertices with no induced subgraphs isomorphic to a P5 or complement of a P5, where P5 = path on 5 vertices.

Original entry on oeis.org

1, 2, 4, 11, 32, 120, 498, 2425, 13107, 79002, 526502, 3918731, 33238798, 334851298, 4273597722

Offset: 1

Jim Nastos, Jul 07 2025

These numbers include both connected and disconnected graphs.

Cf. A000088.

Euler transform of A079564.

def has_induced_P5(g):
    n = g.order()
    if n < 5:
        return False
    from itertools import combinations
    for vertices in combinations(range(n), 5):
        subgraph = g.subgraph(vertices)
        if subgraph.is_isomorphic(graphs.PathGraph(5)):
            return True
    return False
for n in range(3, 11):
    count = 0
    max_edges = n * (n - 1) // 2
    for g in graphs.nauty_geng(f"{n}"):
        edge_count = g.size()
        if edge_count < max_edges / 2:
            if not has_induced_P5(g) and not has_induced_P5(g.complement()):
                count += 2
        elif edge_count == max_edges / 2:
            if not has_induced_P5(g) and not has_induced_P5(g.complement()):
                count += 1
    print(f"n = {n}: {count} graphs with no P5 in G or co-G")

a(9)-a(15) from Sean A. Irvine, Jul 22 2025

A182274 Starting with 1, the smallest number not yet in the sequence such that the sum of every pair of adjacent digits in the sequence sum to a square number.

Original entry on oeis.org

1, 3, 6, 31, 8, 10, 4, 5, 40, 9, 7, 2, 22, 27, 90, 13, 18, 81, 36, 310, 45, 400, 97, 222, 72, 79, 722, 227, 272, 279, 727, 900, 100, 101, 88, 104, 54, 540, 109, 790, 131, 313, 63, 136, 318, 181, 363, 188, 810, 401, 813, 631, 818, 881, 888, 1000, 404, 545, 409

Offset: 1

Jim Nastos, Apr 22 2012

A182271 Starting with 1, smallest integer not yet in the sequence such that two neighboring digits of the sequence multiply to a prime.

Original entry on oeis.org

1, 2, 12, 13, 15, 17, 121, 3, 131, 5, 151, 7, 171, 21, 31, 51, 71, 212, 1212, 1213, 1215, 1217, 1312, 1313, 1315, 1317, 1512, 1513, 1515, 1517, 1712, 1713, 1715, 1717, 12121, 213, 12131, 215, 12151, 217, 12171, 312, 13121, 313, 13131, 315, 13151, 317, 13171

Offset: 1

Eric Angelini and Jim Nastos, Apr 22 2012

Dominic McCarty, Table of n, a(n) for n = 1..10000

a = []
while len(a) < 49:
    a.append(1)
    while (s := "".join(map(str,a))) and a[-1] in a[:-1] or any(s[i] != "1" for i in range(0,len(s),2)) or any(int(s[i]) not in [2,3,5,7] for i in range(1,len(s),2)): a[-1] += 1
print(a) # Dominic McCarty, Jun 14 2025

A182272 Starting with 1, smallest integer not yet in the sequence such that two neighboring digits in the sequence multiply to a composite.

Original entry on oeis.org

1, 4, 2, 3, 5, 6, 7, 8, 9, 10, 14, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76

Offset: 1

Jim Nastos and Eric Angelini, Apr 22 2012

For this sequence, 0 is considered composite.

Dominic McCarty, Table of n, a(n) for n = 1..10000

a, z = [1], [1, 2, 3, 5, 7]
while len(a) < 100:
    k, s = 2, "2"
    while (k in a) or (a[-1] % 10 * int(s[0]) in z) or \
        any(int(s[n]) * int(s[n+1]) in z for n in range(0, len(s)-1)): s, k = str(k+1), k+1
    a.append(k)
print(a) # Dominic McCarty, Feb 05 2025

A182273 Starting with 1, smallest integer not having a zero and not yet in the sequence such that two neighboring digits of the sequence multiply to a composite.

Original entry on oeis.org

1, 4, 2, 3, 5, 6, 7, 8, 9, 14, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84

Offset: 1

Jim Nastos and Eric Angelini, Apr 22 2012

The number after 1 has to be 4, because the product 1*4 must be composite.
Then 2 is OK, because 4*2 = 8 is composite.
Then 3, because 2*3 = 6 is composite, and so on.
Note that 14 is the term after 9 because 10 is now the smallest candidate, but 10 has a 0 digit, 11 consists of two unit digits, and 12 and 13 have digit products 2 and 3, which are prime. - T. D. Noe, Apr 25 2012

Dominic McCarty, Table of n, a(n) for n = 1..10000

Cf. A182272.

a, z = [1], [1,2,3,5,7]
while len(a) < 100:
    k, s = 2, "2"
    while (k in a) or ("0" in s) or (a[-1] % 10 * int(s[0]) in z) or \
        any(int(s[n]) * int(s[n+1]) in z for n in range(0, len(s)-1)): s, k = str(k+1), k+1
    a.append(k)
print(a) # Dominic McCarty, Jan 30 2025

A182177 Beginning with 0, smallest positive integer not yet in the sequence such that two adjacent digits of the sequence (also ignoring commas between terms) sum to a prime.

Original entry on oeis.org

0, 2, 1, 4, 3, 8, 5, 6, 7, 41, 11, 12, 9, 20, 21, 14, 16, 50, 23, 25, 29, 43, 47, 49, 83, 85, 61, 65, 67, 411, 111, 112, 30, 32, 34, 38, 52, 56, 58, 92, 94, 70, 74, 76, 114, 98, 302, 116, 120, 202, 121, 123, 89, 203, 205, 207, 412, 125, 211, 129, 212, 141, 143, 214, 147, 414, 149, 216, 161, 165, 230, 232, 167, 416, 502, 303, 234, 305, 238, 307, 430, 250, 252, 320, 256, 503, 258, 321, 292, 323, 294, 325, 298, 329, 432, 341, 434, 343, 438, 347, 470, 349

Offset: 1

Jim Nastos and Eric Angelini, Apr 16 2012

A219250 is the analog of this sequence, replacing "sum" by "absolute difference". A219249 is the same analog for A182178. A219248 is the analog of A182175 and A219251 corresponds to A219110 = terms which do not occur in this sequence, i.e., the complement of its range. - M. F. Hasler, Apr 12 2013

			41 appears after 7 because 7+4 is prime and 4+1 is prime, and no other number less than 41 (not already in the sequence) satisfies this property. Example: 11 does not directly follow 7 since 7+1 is not prime.

Cf. A182175.

A182177_vec={(n, a=[0], u=0)->while(#aM. F. Hasler, Apr 11 2013

A182175 Numbers with the property that every pair of adjacent digits sum to a prime number.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 20, 21, 23, 25, 29, 30, 32, 34, 38, 41, 43, 47, 49, 50, 52, 56, 58, 61, 65, 67, 70, 74, 76, 83, 85, 89, 92, 94, 98, 111, 112, 114, 116, 120, 121, 123, 125, 129, 141, 143, 147, 149, 161, 165, 167, 202, 203, 205, 207, 211, 212, 214, 216, 230, 232, 234

Offset: 1

Jim Nastos, Apr 16 2012

Complement of A219110. - M. F. Hasler, Apr 11 2013

			983 is in the sequence since 9+8 is prime and 8+3 is prime.

Zak Seidov, Table of n, a(n) for n = 1..10000

These are the candidate numbers for extending A182178.

Cf. A219110.

N:= 4: # to get all terms with up to N digits.
for p from 0 to 9 do P[p]:= select(t -> isprime(t+p),[$0..9]) od:
F:= proc(t) local r,p; r:= t mod 10; op(map(`+`,P[r],10*t)) end proc:
S[1]:= {$1..9}:
for j from 2 to N do S[j]:= map(F,S[j-1]) od:
`union`({0},seq(S[j],j=1..N));
# if using Maple 11 or lower, uncomment the next line:
# sort(convert(%,list));
# Robert Israel, Oct 27 2014

fQ[n_] := Module[{d = IntegerDigits[n], s}, s = Most[d] + Rest[d]; And @@ PrimeQ[s]]; Flatten[Join[{Range[0,9],Select[Range[11, 300], fQ]}]] (* T. D. Noe, Aug 21 2012 and Apr 17 2013; modified by Zak Seidov, Oct 28 2014 *)

is_A182175(n)=!for(i=2, #n=digits(n), isprime(n[i-1]+n[i])||return) \\ M. F. Hasler, Oct 27 2014

cp's OEIS Frontend

User: Jim Nastos

A385156 The number of undirected, simple, unlabeled graphs G on n vertices which are prime, not split, and do not contain a vertex of degree 1 in G or in the complement of G, and has no induced P5 in G or in the complement of G.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A385929 Number of simple, undirected, prime graphs G on n unlabeled vertices with no degree-1 vertex in G or its complement, as well as having no induced P5 in G or in its complement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A385693 Number of prime graphs, G, on n vertices which do not contain a degree-1 vertex in G nor in co-G.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

A385697 Number of unlabeled simple graphs on n vertices with no induced subgraphs isomorphic to a P5 or complement of a P5, where P5 = path on 5 vertices.

Views

Author

Keywords

Comments

Crossrefs

Programs

Sage

Extensions

A182274 Starting with 1, the smallest number not yet in the sequence such that the sum of every pair of adjacent digits in the sequence sum to a square number.

Views

Author

Keywords

A182271 Starting with 1, smallest integer not yet in the sequence such that two neighboring digits of the sequence multiply to a prime.

Views

Author

Keywords

Links

Programs

Python

A182272 Starting with 1, smallest integer not yet in the sequence such that two neighboring digits in the sequence multiply to a composite.

Views

Author

Keywords

Comments

Links

Programs

Python

A182273 Starting with 1, smallest integer not having a zero and not yet in the sequence such that two neighboring digits of the sequence multiply to a composite.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A182177 Beginning with 0, smallest positive integer not yet in the sequence such that two adjacent digits of the sequence (also ignoring commas between terms) sum to a prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A182175 Numbers with the property that every pair of adjacent digits sum to a prime number.

Views

Author

Keywords