Russell Y. Webb - cp's OEIS frontend

A375496 Nonnegative integers k which have a unique minimum length construction starting from 1 and choosing operations f(x) = 3x+1 or g(x) = floor(x/2).

0, 1, 2, 4, 6, 7, 9, 11, 13, 17, 19, 20, 22, 26, 28, 29, 33, 34, 40, 42, 44, 51, 52, 58, 60, 61, 63, 67, 78, 79, 85, 87, 88, 90, 92, 100, 101, 103, 117, 119, 121, 127, 128, 132, 133, 135, 150, 152, 154, 155, 157, 175, 179, 181, 182, 184, 190, 191, 198, 200, 202, 225, 231, 233, 235

Offset: 0

Russell Y. Webb, Aug 31 2024

nonn

A375495(k) is the number of ways to reach k by the minimum length construction and the present sequence is those k for which A375495(k) = 1.
This sequence is infinite, since k = f(f(f(...(1)))) (A003462) is always a unique minimum construction.
Experimentally, it is observed that many of the integers with unique smallest constructions have one or more g(x) steps in their construction and the position of those g(x) operations does not follow an obvious pattern; meaning that these unique constructions are complex and may be related to the complexity of the Hailstone sequences (A127933).

			9 is a term since the shortest sequence of f and g to reach 9 (length A375494(9) = 5) is unique g(f(g(f(f(1))))) = 9.
Here are some of the unique, smallest constructions. All other positive integers smaller than 28 do not have unique, smallest constructions.
0 = g(1)
1 = 1
2 = g◦f(1)
4 = f(1)
6 = g◦f◦f(1)
7 = f◦g◦f(1)
9 = g◦f◦g◦f◦f(1)
11 = g◦f◦f◦g◦f(1)
13 = f◦f(1)
17 = g◦f◦g◦f◦f◦g◦f(1)
19 = f◦g◦f◦f(1)
20 = g◦f◦f◦f(1)
22 = f◦f◦g◦f(1)
26 = g◦f◦g◦f◦g◦f◦f◦g◦f(1)
28 = f◦g◦f◦g◦f◦f(1)

Cf. A375494 (minimum steps), A375495 (ways attained).

from itertools import product
seq = [None for _ in range(200)]
num = [   0 for _ in range(len(seq))]
for L in range(0, 23):
   for P in product((True, False), repeat=L):
      x = 1
      for upward in P:
         x = 3*x+1 if upward else x//2
      if x < len(seq):
         if num[x] == 0 or L < seq[x]:
            seq[x], num[x] = L, 1
         elif L == seq[x]:
            num[x] += 1
print(', '.join([str(i) for i,x in enumerate(num) if x==1]))

A375495 a(n) = number of different ways of selecting the minimum number of operations chosen from f(x) = 3x+1 and g(x) = floor(x/2) needed to reach n when starting from 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 1, 1, 6, 1, 3, 1, 14, 1, 2, 5, 5, 1, 28, 1, 1, 4, 1, 9, 5, 9, 1, 48, 1, 1, 2, 3, 10, 1, 1, 15, 5, 23, 12, 2, 1, 131, 1, 3, 1, 4, 6, 3, 20, 5, 2, 1, 1, 27, 5, 43, 34, 25, 1, 4, 1, 1, 332, 1, 5, 5, 2, 1, 10, 8, 12, 3, 37, 5, 5, 4, 10, 2, 1, 1, 39, 5, 63, 68, 67

Offset: 0

Russell Y. Webb, Aug 18 2024

nonn

The minimum number of operations is A375494(n) and that minimum is attained by a(n) different sequences of operations.

Cf. A375494 (number of operations), A375496 (indices of 1's).

from itertools import product
seq = [None for _ in range(200)]
num = [   0 for _ in range(len(seq))]
for L in range(0, 23):
   for P in product((True, False), repeat=L):
      x = 1
      for upward in P:
         x = 3*x+1 if upward else x//2
      if x < len(seq):
         if num[x] == 0 or L < seq[x]:
            seq[x], num[x] = L, 1
         elif L == seq[x]:
            num[x] += 1
print(', '.join([str(x) for x in num]))

A375494 a(n) = minimum number of operations chosen from f(x) = 3x+1 and g(x) = floor(x/2) needed to reach n when starting from 1.

Original entry on oeis.org

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

Offset: 0

Russell Y. Webb, Aug 18 2024

nonn

The Collatz problems (related problems known by various names, see references) involve iterating the Collatz Mapping (A006370) which applies either 3n+1 or n/2 iteratively when n is odd or even respectively. Considering f(x)=3x+1 and g(x)=x/2 as integer operations of interest, we ask what is the shortest sequence of these operation that produces the nonnegative integers starting with x_0=1. One is chosen as the starting value since producing the number one is the stopping condition for the Hailstone sequences (A006577). The number of distinct shortest sequences of operations (A375495) and the numbers with unique, shortest constructions (A375496) are also of interest.

Seems likely there is a sequence of f and g starting from 1 to reach each nonnegative integer, but a proof has not been proposed.

			For example, to start with 1 and produce the number 7. The shortest sequence is unique and length 3: (3*x+1, floor(x/2), 3*x+1) = f(g(f(x_0))), which follows the trajectory x_0=1, x_1=4, x_2=2, x_3=7.

Eric Weisstein's World of Mathematics, Collatz Problem

Cf. A375495 (number of ways), A375496 (with unique way).

Cf. A125731.

from itertools import product
seq = [None for _ in range(200)]
num = [   0 for _ in range(len(seq))]
for L in range(0, 23):
   for P in product((True, False), repeat=L):
      x = 1
      for upward in P:
         x = 3*x+1 if upward else x//2
      if x < len(seq):
         if num[x] == 0 or L < seq[x]:
            seq[x], num[x] = L, 1
         elif L == seq[x]:
            num[x] += 1
print(', '.join([str(x) for x in seq]))

A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange.

Original entry on oeis.org

1, 0, 4, 80, 4704, 436992, 58897920, 10880501760, 2640513576960, 814928486400000, 311763576754667520, 144816978675459686400, 80294888451877031116800, 52385405443881146567884800, 39727727942688305214337843200, 34656123210118214086941474816000

Offset: 0

Russell Y. Webb, Dec 25 2018

nonn

The sequence is the number of unique arrangements of directed graphs connecting 2*n vertices, where vertices occur in pairs, and meeting the following requirements:
1. Each vertex has an out-degree and in-degree of 1.
2. No edge connects vertices that are paired.
3. Starting with any pair, following the edges of paired vertices connects all vertices.
The requirements were chosen to yield a nice gift exchange between a set of couples. Acknowledgement to the additional members of the initial, inspirational gift exchange group: Cat, Brad, Kim, Ada, Graham, Nolan, and Leah.
The fraction of graphs meeting the requirements is approximately 0.12. Starting with n=2, the fractions are (0.166666667, 0.111111111, 0.116666667, 0.12042328, 0.122959756, 0.124807468). Is there a way to compute the percentage of graphs satisfying the condition in the limit as n approaches infinity?

			For n = 1, there is one pair; a(1) = 0 since requirements 1 and 2 can't be satisfied.
For n = 2, there are two pairs; a(2) = 4 graphs given by these edge destinations:
    ((2, 3), (1, 0))
    ((2, 3), (0, 1))
    ((3, 2), (1, 0))
    ((3, 2), (0, 1)).

Andrew Howroyd, Table of n, a(n) for n = 0..100

A322750 does not allow reciprocal connections.
A010050 is the number of graphs (2n)!.
Cf. A000316, A003471.

\\ Here B(n) gives A003471 as vector.
B(n)={my(v=vector(n+1)); v[1]=1; for(n=4, n, my(m = 2-n%2); v[n+1] = v[n]*(n-1) + 2*(n-m)*v[n-2*m+1]); v}
seq(n)={my(v=B(2*n)); Vec(serlaplace(1+log(sum(k=0, n, v[1+2*k]*x^k/k!, O(x*x^n)))))} \\ Andrew Howroyd, Jan 13 2024

from itertools import permutations as perm
def num_connected_by_pairs(assigned, here=0, seen=None):
    seen = (seen, set())[seen is None]
    for proposed in [(here - 1, here), (here, here + 1)][(here % 2) == 0]:
        if proposed not in seen:
            seen.add(proposed)
            num_connected_by_pairs(assigned, assigned[proposed], seen)
    return len(seen)
def valid(assigned, pairs):
    self_give = [assigned[i] == i for i in range(len(assigned))]
    same_pair = [assigned[i] == i + 1 or assigned[i+1] == i for i in range(0, 2*pairs, 2)]
    if pairs == 0 or True in self_give + same_pair:
        return False
    num_connected = [num_connected_by_pairs(assigned, here) for here in range(2, 2*pairs, 2)]
    return min(num_connected) == 2*pairs
print([len([x for x in perm(range(2*pairs)) if valid(x, pairs)]) for pairs in range(0, 6)])

E.g.f.: 1 + log(B(x)) where B(x) is the e.g.f. of A000316. - Andrew Howroyd, Jan 13 2024

a(0) changed to 1 and a(8) onwards from Andrew Howroyd, Jan 13 2024

A322750 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange with no reciprocal gifts.

Original entry on oeis.org

0, 0, 2, 48, 2640, 250368, 34110720, 6347520000

Offset: 0

Russell Y. Webb, Dec 25 2018

The sequence is the number of unique arrangements of directed graphs connecting 2*n vertices, where vertices occur in pairs, and meeting the following requirements:
1. Each vertex has an out-degree and in-degree of 1.
2. No edge connects vertices that are paired.
3. Starting with any pair, following the edges of paired vertices connects all vertices.
4. There are no closed walks of two vertices (i.e., no reciprocal connections).
The requirements were chosen to yield a nice gift exchange between a set of couples. Acknowledgement to the additional members of the initial, inspirational gift exchange group: Cat, Brad, Kim, Ada, Graham, Nolan, and Leah.
The fraction of graphs meeting the requirements is approximately 0.07. Starting with n=2, the fractions are (0.083333333, 0.066666667, 0.06547619, 0.068994709, 0.071212121, 0.072810787). Is there a way to compute the percentage of graphs satisfying the condition in the limit as n approaches infinity?

			For n = 0, there are no pairs; a(0) = 0 since no edges exist.
For n = 1, there is one pair; a(1) = 0 since requirements 1 and 2 can't be satisfied.
For n = 2, there are two pairs; a(2) = 2 graphs given by these edge destinations:
    ((2, 3), (1, 0))
    ((3, 2), (0, 1))
while ((2, 3), (0, 1)) is not allowed because the first and third edges form a 2-vertex walk.

A322751 allows reciprocal connections.

A010050 is the number of graphs (2n)!.

from itertools import permutations as perm
def num_connected_by_pairs(assigned, here=0, seen=None):
    seen = (seen, set())[seen is None]
    for proposed in [(here - 1, here), (here, here + 1)][(here % 2) == 0]:
        if proposed not in seen:
            seen.add(proposed)
            num_connected_by_pairs(assigned, assigned[proposed], seen)
    return len(seen)
def valid(assigned, pairs):
    self_give = [assigned[i] == i for i in range(len(assigned))]
    is_reciprocal = [assigned[a] == i for i, a in enumerate(assigned)]
    same_pair = [assigned[i] == i + 1 or assigned[i+1] == i for i in range(0, 2*pairs, 2)]
    if pairs == 0 or True in self_give + is_reciprocal + same_pair:
        return False
    num_connected = [num_connected_by_pairs(assigned, here) for here in range(2, 2*pairs, 2)]
    return min(num_connected) == 2*pairs
print([len([x for x in perm(range(2*pairs)) if valid(x, pairs)]) for pairs in range(0, 6)])

A321340 a(1) = 1; thereafter a(n) = a(n-1) * prime(n-1)^a(n-1).

Original entry on oeis.org

1, 2, 18, 68664550781250

Offset: 1

Russell Y. Webb, Nov 05 2018

nonn

The prime factorization of a(n) describes all previous terms in the sequence: a(n) = prime(1)^a(1) * prime(2)^a(2) * prime(3)^a(3) * ...* prime(n-1)^a(n-1).

An infinite and monotonically increasing sequence which grows very rapidly.

			68664550781250 = 2 * 3^2 * 5^18 = prime(1)^1 * prime(2)^2 * prime(3)^18.

Somewhat similar to A007097.

Cf. A321339.

Nest[Append[#, #[[-1]] Prime[Length@ #]^#[[-1]] ] &, {1}, 3] (* Michael De Vlieger, Nov 05 2018 *)

apply( ppp(n) = prod(i=1, n-1, prime(i)^ppp(i)), [1..4] )

A321339 a(1)=1; thereafter a(n) = a(n-1) * prime(a(n-1))^(n-1).

Original entry on oeis.org

1, 2, 18, 4085658, 94856826320432984953640661130233988218

Offset: 1

Russell Y. Webb, Nov 05 2018

nonn

The prime factorization of a(n) describes all previous terms in the sequence: a(n) = prime(a(1))^1 * prime(a(2))^2 * prime(a(3))^3 * ...* prime(a(n-1))^(n-1).

An infinite and monotonically increasing sequence. Grows fast enough that a(6) and later terms are too large to display in full.

			4085658 = 2 * 3^2 *61^3 = prime(1)^1 * prime(2)^2 * prime(18)^3. The previous values in the sequence can be read from this factorization: the 3rd is 18, the 2nd is 2, the 1st is 1.

Somewhat similar to A007097.

Cf. A321340.

Nest[Append[#, #[[-1]] Prime[#[[-1]] ]^Length@ #] &, {1}, 4] (* Michael De Vlieger, Nov 05 2018 *)
nxt[{n_,a_}]:={n+1,a*Prime[a]^n}; NestList[nxt,{1,1},4][[All,2]] (* Harvey P. Dale, May 28 2019 *)

apply( a(n) = prod(i=1, n-1, prime(a(i))^i), [1..5] )

A256623 Number of distinct n-digit patterns in base 10 such that the pattern and its reverse are prime.

Original entry on oeis.org

4, 5, 29, 102, 796, 4769, 35905, 267789, 2101184, 16809690, 137487157, 1147385627, 9745119882

Offset: 1

Russell Y. Webb, Jul 11 2015

Here, distinct numbers means under reversal. 13 and 31 are the same pattern under reversal and only count as one. The sequence can be calculated from the number of palindrome primes (A016115), p_i, and number of reversal primes (A048054), r_i. X_i = (r_i - p_i)/2 + p_i. The (r_i - p_i) term is always even, by construction (it is the count of reversible primes that are not their own reverse).
This sequence is the set cardinality of the prime numbers under a base-10 digit reversal identity operator.
Since there are no palindrome primes with even digits > 11 we know that the even entries are the same as half the number of reversible primes.

Cf. A016115, A048054.

a(n) = (A048054(n) + A016115(n))/2.

a(11)-a(13) from Giovanni Resta, Jul 19 2015

A140460 a(0) = 2; thereafter a(n) = smallest integer not a multiple of an earlier terms nor a sum of two earlier terms.

Original entry on oeis.org

2, 3, 7, 11, 17, 23, 29, 37, 41, 47, 53, 59, 65, 71, 79, 83, 89, 95, 101, 107, 113, 125, 131, 137, 149, 155, 163, 167, 173, 179, 191, 197, 211, 215, 223, 227, 233, 239, 247, 251, 257, 263, 269, 277, 281, 293, 305, 311, 317, 331, 335

Offset: 0

Russell Y. Webb (r.webb(AT)elec.canterbury.ac.nz), Jul 22 2008

Note that the first composite value is a(12) = 65 = 5 * 13, since 5 and 13 are the first two primes sieved out of the sequence. Similarly, the second composite value is a(17) = 95 = 5 * 19, since 5 and 19 are the first and third primes sieved out of the sequence. - Jonathan Vos Post, Jul 27 2008

Nathaniel Johnston, Table of n, a(n) for n = 0..10000

Cf. A000040, A002858, A008320, A054016, A075573, A085947.

#include 
#include 
void sieve(){ const int first = 2; const int max = 10000; bool member[max]; for(int i = first; i < max; ++i){ member[i] = true; } for(int i = first; i < max; ++i){ if(member[i]){ for(int x = i + i; x < max; x += i){ member[x] = false; } for(int j = first; j < i; ++j){ if(member[j] && i + j < max){ member[i + j] = false; } } } } int num = 0; for(int i = first; i < max; ++i){ if(member[i]){ printf("%i, ", i); num += 1; } } printf(" num = %i ", num); }

s={2};Do[m=2;Until[Total[Boole[Divisible[m,s]]]==0&&!MemberQ[Total/@Subsets[s,{2}],m],m++];AppendTo[s,m],{n,50}];s (* James C. McMahon, Jul 09 2025 *)

cp's OEIS Frontend

User: Russell Y. Webb

A375496 Nonnegative integers k which have a unique minimum length construction starting from 1 and choosing operations f(x) = 3x+1 or g(x) = floor(x/2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A375495 a(n) = number of different ways of selecting the minimum number of operations chosen from f(x) = 3x+1 and g(x) = floor(x/2) needed to reach n when starting from 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

A375494 a(n) = minimum number of operations chosen from f(x) = 3x+1 and g(x) = floor(x/2) needed to reach n when starting from 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A322751 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A322750 Number of directed graphs of 2*n vertices each having an in-degree and out-degree of 1 such that the graph specifies a pairwise connected gift exchange with no reciprocal gifts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A321340 a(1) = 1; thereafter a(n) = a(n-1) * prime(n-1)^a(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A321339 a(1)=1; thereafter a(n) = a(n-1) * prime(a(n-1))^(n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A256623 Number of distinct n-digit patterns in base 10 such that the pattern and its reverse are prime.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A140460 a(0) = 2; thereafter a(n) = smallest integer not a multiple of an earlier terms nor a sum of two earlier terms.