A261144 -id:A261144 - cp's OEIS frontend

A322370 For any n > 4: let p be the n-th prime number; a(n) is the least squarefree p-smooth integer congruent to 4 modulo p.

15, 30, 21, 42, 119, 33, 35, 78, 209, 133, 51, 57, 299, 65, 138, 217, 77, 399, 87, 93, 295, 105, 210, 111, 222, 230, 258, 266, 141, 143, 451, 155, 161, 330, 505, 177, 183, 185, 195, 390, 201, 203, 215, 1342, 231, 462, 237, 721, 1209, 255, 518, 267, 273, 546

Offset: 5

Rémy Sigrist, Dec 05 2018

nonn

This sequence is well-defined per the work of Booker and Pomerance.

The number 4 in the congruence in the name could be replaced by any value; this number was chosen for being the first integer that is not squarefree.

			For n = 7:
- the 7th prime is 17,
- the first squarefree 17-smooth integers s, alongside (s-4) mod 17, are:
     s              1   2   3  5  6  7  10  11  13  14  15  17  21
     ------------  --  --  --  -  -  -  --  --  --  --  --  --  --
     (s-4) mod 17  14  15  16  1  2  3   6   7   9  10  11  13   0
- hence a(7) = 21.

Rémy Sigrist, Table of n, a(n) for n = 5..10000
Andrew R. Booker, Carl Pomerance, Squarefree smooth numbers and Euclidean prime generators, arXiv:1607.01557 [math.NT], 2016-2017.
Andrew R. Booker and Carl Pomerance, Squarefree smooth numbers and Euclidean prime generators, Proceedings of the American Mathematical Society 145 (2017), 5035-5042.
Rémy Sigrist, Colored scatterplot of (n, a(n)) for n = 5..1000000 (where the color is function of (a(n)-4)/A000040(n)).

Cf. A000040, A005117, A261144.

a[n_] := Module[{p = Prime[n], k = 4}, While[! SquareFreeQ[k] || FactorInteger[k][[-1, 1]] > p, k += p; Continue[]]; k]; Array[a, 100, 5] (* Amiram Eldar, Dec 08 2018 *)

a(n) = my (p=prime(n)); forstep (v=4, oo, p, if (issquarefree(v), my (f=factor(v)); if (f[#f~,1] <= p, return (v))))

a(n) = A261144(n, k) for some k in 1..2^n.

A277428 a(n) = the n-bit number in which the i-th bit is 1 if and only if prime(i) divides A060795(n).

Original entry on oeis.org

0, 1, 4, 9, 11, 22, 75, 105, 449, 425, 1426, 2837, 4765, 2775, 21895, 57558, 87602, 145177, 123788, 694479, 677326, 1516496, 3363284, 2048443, 26968428, 24488513, 98733728

Offset: 1

Luc Rousseau, Oct 14 2016

a(n) is also the n-bit number in which the i-th bit is 1 if and only if prime(i) does not divide A060796(n).
a(n) is also the encoding of the fraction defined as follows:
Consider the set of fractions that can be built by only using each prime number from prime(1) to prime(n) exactly once as factors, either in the numerator or in the numerator. There are 2^n such fractions. One of them, let's call it x, has the property of yielding the result nearest to 1. a(n) is the n-bit number in which the i-th bit is 1 if prime(i) appears in the numerator of x, 0 if prime(i) appears in the denominator of x.
Remark: x is A060795(n) / A060796(n). Notice how in this prime-rank-to-bit representation, A060795(n) and A060796(n) are each other's bitwise negation.

			For n = 1, two distinct fractions can be written with the first prime number, namely 1/2 and 2. Of the two, 1/2 is nearer to 1. 1/2 has its 2 below the fraction bar, so its binary encoding is 0, which yields a(1) = 0.
For n = 2, four distinct fractions can be written with the first two prime numbers, namely 1/6, 2/3, 3/2 and 6. 2/3 is the nearest to 1. 2/3 has its 2 above the fraction bar and its 3 below, so its encoding is 01, which yields a(2) = 1.

Encodes A060795 and A060796. Cf. A002110, A261144.

package oeis;
public class BinaryEncodedBestPrimeSetup {
  // Brute force implementation... Can it be improved?
public static int PRIME[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, /* to be continued */ };
public static void main(String args[]) {
  int nMax = PRIME.length; // number of terms of the sequence
  for (int n = 1; n <= nMax; n ++) {
   if (n > 1) {
    System.out.print(", ");
   }
   System.out.print(u(n));
  }
}
private static int u(int n) {
  double bestMul = 0.0;
  int bestSetup = -1;
  int s = 0; // binary-encoded setup number
  for (s = 0; s < (1 << n); s ++) {
   double mul = 1.0;
   int i = 0; // prime number #
   for (i = 0; i < n; i ++) {
    if ((s & (1 << i)) != 0) {
     mul *= PRIME[i]; // 1 = above fraction bar
    } else {
     mul /= PRIME[i]; // 0 = below fraction bar
    }
   }
   if (mul < 1.0) {
    if (mul > bestMul) {
     bestMul = mul;
     bestSetup = s;
    }
   }
  }
  return bestSetup;
}
}

{0}~Join~Table[Function[p, FromDigits[#, 2] &@ Reverse@ MapAt[# + 1 &, ConstantArray[0, n], Partition[#, 1, 1]] &@ PrimePi@ FactorInteger[Numerator@ #][[All, 1]] &@ Max@ Select[Map[p/#^2 &, Divisors@ p], # < 1 &]][Times @@ Prime@ Range@ n], {n, 2, 23}] (* Michael De Vlieger, Oct 19 2016 *)

a060795(n) = my(m=prod(i=1, n, prime(i))); divisors(m)[numdiv(m)\2];
a(n) = {my(a95 = a060795(n)); v = vector(n, i, (a95 % prime(i))==0); subst(Polrev(v), x, 2); } \\ Michel Marcus, Dec 03 2016

a(22)-a(27) from Michael De Vlieger, Oct 19 2016

cp's OEIS Frontend

A322370 For any n > 4: let p be the n-th prime number; a(n) is the least squarefree p-smooth integer congruent to 4 modulo p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula