A280774 -id:A280774 - cp's OEIS frontend

A280864 Lexicographically earliest infinite sequence of distinct positive terms such that, for any prime p, any run of consecutive multiples of p has length exactly 2.

1, 2, 4, 3, 6, 8, 5, 10, 12, 9, 7, 14, 16, 11, 22, 18, 15, 20, 24, 21, 28, 26, 13, 17, 34, 30, 45, 19, 38, 32, 23, 46, 36, 27, 25, 35, 42, 48, 29, 58, 40, 55, 33, 39, 52, 44, 77, 49, 31, 62, 50, 65, 78, 54, 37, 74, 56, 63, 51, 68, 60, 75, 41, 82, 64, 43, 86

Offset: 1

Rémy Sigrist, Jan 09 2017

In other words, each multiple of a prime p has exactly one neighbor that is also a multiple of p.
This sequence is similar to A280866; the first difference occurs at n=42: a(42)=55 whereas A280866(42)=50.
Conjectured to be a permutation of the positive integers.
Sometimes referred to as the "cup of coffee" sequence, since it feels as if just one more cup of coffee is all it would take to prove that this is indeed a permutation of the positive integers. - N. J. A. Sloane, Nov 04 2020
There are several short cycles, and apparently at least two infinite cycles. For a list see the attached file "Properties of A280864". - N. J. A. Sloane, Feb 03 2017
Properties (For proofs, see the attached file "Properties of A280864")
Theorem 1: This sequence contains every prime and every even number. (Added by N. J. A. Sloane, Jan 15 2017)
Theorem 2: The sequence contains infinitely many odd composite numbers. (Added by N. J. A. Sloane, Feb 14 2017)
Theorem 3: If p is an odd prime, the sequence contains infinitely many odd multiples of p. (Added by N. J. A. Sloane, Mar 12 2017, with corrected proof Apr 03 2017)
There are two types of primes in this sequence: Type I, the first time a term a(n) is divisible by p is when a(n)=p for some n; Type II, the first time a term a(n) is divisible by p is when a(n)=k*p for some n and some k>1 (the Type II primes are listed in A280745).
Conjecture 4: If a prime p divides a(n) then p <= n. - N. J. A. Sloane, Apr 07 2017 and Apr 16 2017
Theorem 5: The sequence is a permutation of the natural numbers iff it contains every square. - N. J. A. Sloane, Apr 14 2017
From Bob Selcoe, Apr 03 2017: (Start)
Define the "radical class" C_R to be the set of numbers which have the same radical R (or the same largest squarefree divisor - i.e., the same product of their prime factors). These are the columns in A284311. So for example C_10 is the set of numbers with radical 10 or prime factors {2,5}: {10, 20, 40, 50, 80, 100, 160, ...}.
If the sequence contains any members of C_R, then those members must appear in order; so for example, if 160 has appeared, {10, 20, 40, 50, 80} will have already appeared, in that order. Naturally, this holds for prime powers; for example, C_5: if 3125 has appeared, {5, 25, 125, 625} will have appeared earlier, in that order.
After seeing a(n), let S be smallest missing number (A280740) and let prime(G) be largest prime already appearing in the sequence. Conjecture: Prime(G) < S <= prime(G+1), and a(35) = 25 = S is the only nonprime S term (following a(31) = 23, preceding a(39) = 29). (End)

			The first terms, alongside their required and forbidden prime factors are:
n   a(n)  Required  Forbidden
--  ----  --------  ---------
1      1  none      none
2      2  none      none
3      4  2         none
4      3  none      2
5      6  3         none
6      8  2         3
7      5  none      2
8     10  5         none
9     12  2         5
10     9  3         2
11     7  none      3
12    14  7         none
13    16  2         7
14    11  none      2
15    22  11        none
16    18  2         11
17    15  3         2
18    20  5         3
19    24  2         5
20    21  3         2
21    28  7         3
22    26  2         7
23    13  13        2
24    17  none      13
25    34  17        none
26    30  2         17
27    45  3, 5      2
28    19  none      3, 5
29    38  19        none
30    32  2         19
31    23  none      2
32    46  23        none
33    36  2         23
34    27  3         2
35    25  none      3
36    35  5         none
37    42  7         5
38    48  2, 3      7
39    29  none      2, 3
40    58  29        none
41    40  2         29
42    55  5         2

N. J. A. Sloane, Table of n, a(n) for n = 1..100000 (First 10000 terms from Rémy Sigrist)
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
Rémy Sigrist, PARI program for A280864
N. J. A. Sloane, Properties of A280864 [Revised, Apr 25 2017]
N. J. A. Sloane, Table of n, a(n) for n = 1..1000000, computed using Sigrist's PARI program.
N. J. A. Sloane, Confessions of a Sequence Addict (AofA2017), slides of invited talk given at AofA 2017, Jun 19 2017, Princeton. Mentions this sequence.

See A280738, A280740, A280741 (inverse), A280742, A280743, A280744, A280745, A280746, A280755, A280770, A280771, A280773, A280774, A283832, A284724, A284725, A284726, A284785, A285181 for various subsidiary sequences.
A280754 gives fixed points.
Cf. A280866.
In the same spirit as A064413 and A098550.
A338338, A338444, and A375029 are variants.
A373797 is a finite version.

N:= 1000: # to get all terms until the first term > N
A[1]:= 1:
A[2]:= 2:
G:= {}:
Avail:= [$3..N]:
found:= true:
lastn:= 2:
for n from 3 while found and nops(Avail)>0 do
  found:= false;
  H:= G;
  G:= numtheory:-factorset(A[n-1]);
  r:= convert(G minus H,`*`);
  s:= convert(G intersect H, `*`);
  for j from 1 to nops(Avail) do
    if Avail[j] mod r = 0 and igcd(Avail[j],s) = 1 then
      found:= true;
      A[n]:= Avail[j];
      Avail:= subsop(j=NULL,Avail);
      lastn:= n;
      break
    fi
  od;
od:
seq(A[i],i=1..lastn); # Robert Israel, Mar 22 2017

terms = 100;
rad[n_] := Times @@ FactorInteger[n][[All, 1]];
A280864 = Reap[present = 0; p = 1; pp = 1; Do[forbidden = GCD[p, pp]; mandatory = p/forbidden; a = mandatory; While[BitGet[present, a] > 0 || GCD[forbidden, a] > 1, a += mandatory]; Sow[a]; present += 2^a; pp = p; p = rad[a], terms]][[2, 1]] (* Jean-François Alcover, Nov 23 2017, translated from Rémy Sigrist's PARI program *)

Added "infinite" to definition. - N. J. A. Sloane, Sep 28 2019

A373797 a(n) = maximal k such that there exists a sequence S = [s_1, s_2, ..., s_k] with s_i distinct and in the range 1 <= s_i <= n such that if any s_i is divisible by a prime p, then p also divides exactly one of s_{i-1} and s_{i+1}.

Original entry on oeis.org

1, 1, 1, 3, 3, 4, 4, 6, 6, 8, 8, 10, 10, 11, 11, 13, 13, 14, 14, 16, 16, 17, 17, 19, 19, 21, 22, 24, 24, 25, 25

Offset: 1

N. J. A. Sloane, Jul 26 2024

This is a finite version of the "cup of coffee" sequence A280864.
An obvious upper bound is a(n) <= n-C, where C is the number of primes p <= n such that 2*p > n. For example a(4) <= 3, since we cannot make use of the prime 3.
Note that for a prime p <= n/2, the number of terms in S that are divisible by p must be even. So if floor(n/p) is odd for any p <= n/2, we have a(n) <= n-C-1.
When going from n=p-1 to n=p (where p is a prime), the new p cannot be used, so a(p) = a(p-1) for p prime.
We can obtain a sequence of lower bounds by taking S to consist of the first A280774(m) terms of A280864, for m = 1,2,3,...  This gives
   a(m) >= max_{1 <= i <= A280774(m)} A280864(i).... (**)
 For example, with m=4, we can take the first A280774(4) = 10 terms of A280864, that is, the sequence S = 1,2,4,3,6,8,5,10,12,9, to get a(12) >= 10.  In fact equality holds: a(12) = 10 (see EXAMPLES below).
It was possible that equality would always hold in (**). (**) gives a(4) >= 3, a(8) >= 6, a(12) >= 10, a(16) >= 13 (equality holds up to this point), then a(28) >= 23, a(45) >= 27, ... However, Rémy Sigrist has shown that a(28) = 24.
a(24) = 19 so a(25) >= 19. Here is an argument that shows that a(25) = 20 is impossible. We can't use the big primes 13 17 19 23. There are 5 multiples of 5 we could use, 5 10 15 20 25, but we can only use 4 of them.  There are 3 multiples of 7 we could use, namely 7 14 21, but we can only use 2 of them. These two lists are disjoint. So a(25) >= 25 - 4 - 2 = 19. - N. J. A. Sloane, Jul 27 2024

			Solutions for small n (the solutions are a long way from being unique, but see A375030):
  n   a(n)    Solution S
  1    1        1
  4    3        1,2,4
  6    4        1,2,6,3
  8    6        1,2,4,3,6,8
  10   8        1,2,4,3,9,5,10,8
  12   10       1,2,4,3,6,8,5,10,12,9
  14   11       1,2,4,3,6,10,5,7,14,12,9
  16   13       1,2,4,3,6,8,5,10,12,9,7,14,16
As an example, let us verify that the prime-divisibility condition holds for the n=14 solution (we write Y to indicate divisibility):
  S = 1,2,4,3,6,10,5,7,14,12,9
  2?....Y.Y...Y..Y......Y..Y..
  3?........Y.Y............Y.Y
  5?.............Y.Y..........
  7?.................Y..Y.....
The Y's occur in disjoint pairs, as required.
Also, a(18) = 14, from S = 1,8,16,3,6,14,7,5,15,18,4,9,12,2. (We cannot use 11, 13, and 17, and there are an odd number of multiples of 2 and of 5, so we must lose at least one more term - we can take care of this by sacrificing 10 - so 18-4 = 14 is optimal. This implies a(19) = 14 also.)

Rémy Sigrist, C++ program

Cf. A280864, A280774, A375024, A375029, A375030.

See A373800 for the right-hand side of (**).

from itertools import permutations
from sympy import primefactors, primepi
def A373797(n):
    c = [set()]+[set(primefactors(i)) for i in range(1,n+1)]+[set()]
    for k in range(n-primepi(n)+primepi(n>>1),0,-1):
        for a in permutations(range(1,n+1),k):
            alist = [0]+list(a)+[n+1]
            if all((p in c[alist[i-1]])^(p in c[alist[i+1]]) for i, d in enumerate(alist[1:-1],1) for p in c[d]):
                return k # Chai Wah Wu, Jul 26 2024

# Given a list S = [s_1, s_2, ..., s_k], this function checks if the terms s_i are such that if any s_i is divisible by a prime p, then p also divides exactly one of s_{i-1} and s_{i+1}.
from sympy import primefactors
def isSolution(S: list[int]) -> bool:
    return all(not any((S[i-1] % p == 0) == (S[i+1] % p == 0)
           for p in primefactors(S[i])) for i in range(1, len(S)-1))
# Peter Luschny, Jul 27 2024
(C++) // See Links section.

a(20)-a(24) from Rémy Sigrist, Jul 27 2024
a(25) from N. J. A. Sloane, Jul 27 2024
a(26)-a(31) from Rémy Sigrist, Jul 28 2024

A338450 Numbers k such that A338338(k) and A338338(k+1) are coprime.

Original entry on oeis.org

1, 6, 10, 18, 37, 67, 77, 81, 90, 124, 156, 160, 185, 205, 259, 289, 330, 376, 429, 452, 492, 501, 513, 600, 609, 618, 622, 674, 683, 710, 743, 796, 821, 945, 1038, 1060, 1086, 1214, 1312, 1316, 1493, 1556, 1735, 1764, 1929, 1938, 2052, 2216, 2230, 2259, 2521

Offset: 1

Rémy Sigrist, Oct 28 2020

nonn

			gcd(A338338(6), A338338(7)) = gcd(9, 5) = 1, so 6 belongs to the sequence.
gcd(A338338(2), A338338(3)) = gcd(2, 4) = 2, so 2 does not belong to the sequence.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, C program for A338450

Cf. A280774, A338338.

C
```
See Links section.
```

A370628 a(n) = GCD(A280864(n), A280864(n+1)).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 5, 2, 3, 1, 7, 2, 1, 11, 2, 3, 5, 4, 3, 7, 2, 13, 1, 17, 2, 15, 1, 19, 2, 1, 23, 2, 9, 1, 5, 7, 6, 1, 29, 2, 5, 11, 3, 13, 4, 11, 7, 1, 31, 2, 5, 13, 6, 1, 37, 2, 7, 3, 17, 4, 15, 1, 41, 2, 1, 43, 2, 33, 1, 47, 2, 35, 3, 19, 4, 3, 23, 4, 5

Offset: 1

Rémy Sigrist, May 01 2024

nonn

			a(89) = GCD(A280864(89), A280864(90)) = GCD(90, 135) = 45.

Rémy Sigrist, PARI program

Cf. A007947, A280738, A280774, A280864.

terms = 100;
rad[n_] := Times @@ FactorInteger[n][[All, 1]];
A280864 = Reap[present = 0; p = 1; pp = 1;
    Do[forbidden = GCD[p, pp]; mandatory = p/forbidden;
        a = mandatory;
        While[BitGet[present, a] > 0 || GCD[forbidden, a] > 1,
            a += mandatory];
        Sow[a];
        present += 2^a; pp = p; p = rad[a],
     {terms}]][[2, 1]];
Clear[a];
a[n_] := GCD[A280864[[n]], A280864[[n + 1]]];
Table[a[n], {n, 1, terms - 1}] (* Jean-François Alcover, May 10 2024, adapted from Rémy Sigrist's PARI program *)

PARI
```
\\ See Links section.
```

GCD(a(n), a(n+1)) = 1.
A007947(a(n)) = A280738(n).
a(n) = 1 iff n belongs to A280774.

Let s(m) = A280864(m). The sequence gives the lengths of successive segments when A280864 is split after any term s(m) where every prime divisor of s(m) has already divided s(m-1). (Then s(m+1) is the smallest number not yet in A280864 which is relatively prime to s(m).)

See the link "Properties of A280864" in A280864 for more information.

cp's OEIS Frontend

A283832 First differences of A280774.

Views

Author

Keywords

Comments

Links

Crossrefs

A280864 Lexicographically earliest infinite sequence of distinct positive terms such that, for any prime p, any run of consecutive multiples of p has length exactly 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A373797 a(n) = maximal k such that there exists a sequence S = [s_1, s_2, ..., s_k] with s_i distinct and in the range 1 <= s_i <= n such that if any s_i is divisible by a prime p, then p also divides exactly one of s_{i-1} and s_{i+1}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Extensions

A338450 Numbers k such that A338338(k) and A338338(k+1) are coprime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

C

A370628 a(n) = GCD(A280864(n), A280864(n+1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A285189 k appears A283832(k+1) times.

Views

Author

Keywords

Comments

Crossrefs