A080147 -id:A080147 - cp's OEIS frontend

A267097 a(n) = number of 4k+1 primes among first n primes; least monotonic left inverse of A080147.

0, 0, 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 9, 10, 11, 12, 12, 12, 13, 14, 14, 14, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 20, 21, 21, 21, 21, 21, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 28, 28, 29, 29, 29, 30, 31, 31, 32, 32, 33, 34, 34, 34, 35, 35, 35, 36, 37, 38, 39, 39, 40, 40, 41

Offset: 1

Antti Karttunen, Feb 01 2016

nonn

a(n) = number of 4k+1 primes (A002144) among primes in range 2 .. A000040(n).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000040, A002144, A080147, A267098.

Cf. also A267101.

a[n_]:=Length[Select[Prime[Range[n]],IntegerQ[(#-1)/4] &]]; Array[a,84] (* Stefano Spezia, May 01 2025 *)

Other identities. For all n >= 1:
a(A080147(n)) = n.
a(n) + A267098(n) = n-1.

A267107 "Chebyshev's bat permutation": a(1) = 1, a(A080147(n)) = A080148(a(n)), a(A080148(n)) = A080147(a(n)).

Original entry on oeis.org

1, 3, 2, 7, 6, 5, 4, 16, 13, 14, 12, 11, 9, 10, 35, 8, 29, 31, 30, 26, 23, 25, 21, 27, 22, 20, 24, 74, 17, 19, 18, 62, 67, 66, 15, 65, 54, 57, 51, 58, 55, 56, 45, 48, 43, 59, 50, 44, 53, 47, 39, 152, 49, 37, 41, 42, 38, 40, 46, 144, 130, 32, 139, 137, 36, 34, 33, 118, 136, 129, 128, 113, 121, 28, 108, 122, 125

Offset: 1

Antti Karttunen, Feb 01 2016

This is a self-inverse permutation of natural numbers.

Antti Karttunen, Table of n, a(n) for n = 1..10001
Antti Karttunen, Entanglement Permutations, 2016-2017.
Index entries for sequences that are permutations of the natural numbers

Cf. A000040, A002144, A002145, A038698, A080147, A080148, A267097, A267098.
Cf. A268393 (record positions), A268394 (record values).
Cf. A267100, A267105, A267106 and also A270193, A270194, A270199, A270201, A270202 for other similarly constructed permutations based on prime distribution biases.

allocatemem(2^30);
default(primelimit,4294965247);
uplim = 2^20;
uplim2 = 366824; \\ Very ad hoc.
v080147 = vector(uplim);
v080148 = vector(uplim);
v267097 = vector(uplim);
v267107 = vector(uplim);
v267097[1] = 0; c = 0; v47i = 0; v48i = 0; for(n=2, uplim, if((1 == (prime(n)%4)), c++; v47i++; v080147[v47i] = n, v48i++; v080148[v48i] = n); v267097[n] = c; if(!(n%32768),print1(" n=",n)));
A080147(n) = v080147[n];
A080148(n) = v080148[n];
A267097(n) = v267097[n];
A267098(n) = (n - A267097(n))-1;
A267107(n) = v267107[n];
v267107[1] = 1; for(n=2, uplim2, if((1 == (prime(n) % 4)), v267107[n] = A080148(A267107(A267097(n))), v267107[n] = A080147(A267107(A267098(n))));  if(!(n%32768),print1(" n=",n)));
for(n=1, uplim2, write("b267107.txt", n, " ", A267107(n)));

;; With memoization-macro definec
(definec (A267107 n) (cond ((<= n 1) n) ((= 1 (modulo (A000040 n) 4)) (A080148 (A267107 (A267097 n)))) (else (A080147 (A267107 (A267098 n))))))

a(1) = 1; and for n > 1, if prime(n) modulo 4 = 1, a(n) = A080148(a(A267097(n))), otherwise a(n) = A080147(a(A267098(n))).

Name changed, the old name was "Manta moth permutation" - Antti Karttunen, Dec 10 2019

A267100 Self-inverse permutation of natural numbers: a(1) = 1, a(A080147(n)) = A080148(n), a(A080148(n)) = A080147(n).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Feb 01 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Cf. A000040, A000720, A080147, A080148, A267101, A267097, A267098, A267099.

Cf. also A267107 (a more recursed variant).

a(1) = 1; for n > 1, if prime(n) mod 4 = 1, then a(n) = A080148(A267097(n)), otherwise a(n) = A080147(A267098(n)).
Other identities. For all n >= 1:
a(n) = A000720(A267101(n)).

A267105 Permutation of natural numbers: a(1) = 1, a(A080147(n)) = 1+(2a(n)), a(A080148(n)) = 2a(n).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 12, 9, 10, 13, 11, 14, 16, 15, 24, 17, 18, 20, 25, 26, 22, 19, 21, 27, 28, 32, 23, 29, 30, 48, 33, 34, 31, 36, 49, 40, 50, 35, 52, 37, 44, 41, 51, 38, 42, 54, 56, 53, 45, 64, 39, 46, 43, 58, 55, 60, 57, 65, 96, 47, 66, 68, 59, 61, 62, 97, 72, 67, 69, 98, 80, 63, 100, 70, 73, 99, 81, 101, 104, 71, 74

Offset: 1

Antti Karttunen, Feb 01 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A267106.
Cf. A000040, A002144, A002145, A080147, A080148, A267097, A267098.
Cf. also A267107.

a(1) = 1; and for n > 1, if prime(n) mod 4 = 1, then a(n) = 1 + 2*a(A267097(n)), otherwise a(n) = 2*a(A267098(n)).

A267106 Permutation of natural numbers: a(1) = 1, a(2n) = A080148(a(n)), a(2n+1) = A080147(a(n)).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 10, 11, 13, 9, 12, 14, 16, 15, 18, 19, 24, 20, 25, 23, 29, 17, 21, 22, 26, 27, 30, 31, 35, 28, 33, 34, 40, 36, 42, 46, 53, 38, 44, 47, 55, 43, 51, 54, 62, 32, 37, 39, 45, 41, 50, 48, 57, 49, 59, 56, 65, 58, 66, 67, 74, 52, 60, 63, 70, 64, 71, 76, 82, 69, 77, 83, 87, 91, 98, 101, 112, 73, 79

Offset: 1

Antti Karttunen, Feb 01 2016

This sequence can be represented as a binary tree. Each left hand child is produced as A080148(n), and each right hand child as A080147(n), when the parent node contains n:
                                    |
                 ...................1...................
                2                                       3
      4......../ \........6                   5......../ \........7
     / \                 / \                 / \                 / \
    /   \               /   \               /   \               /   \
   /     \             /     \             /     \             /     \
  8       10         11       13          9       12         14       16
15 18   19  24     20  25   23  29      17 21   22  26     27  30   31  35
etc.

Antti Karttunen, Table of n, a(n) for n = 1..16383
Index entries for sequences that are permutations of the natural numbers

Inverse: A267105.
Cf. A000040, A002144, A002145, A080147, A080148.
Cf. also A267107.

a(1) = 1, after which, a(2n) = A080148(a(n)), a(2n+1) = A080147(a(n)).

A080148 Positions of primes of the form 4*k+3 (A002145) among all primes (A000040).

Original entry on oeis.org

2, 4, 5, 8, 9, 11, 14, 15, 17, 19, 20, 22, 23, 27, 28, 31, 32, 34, 36, 38, 39, 41, 43, 46, 47, 48, 49, 52, 54, 56, 58, 61, 63, 64, 67, 69, 72, 73, 75, 76, 81, 83, 85, 86, 90, 91, 92, 93, 94, 95, 96, 99, 101, 103, 105, 107, 109, 111, 114, 115, 117, 118, 120, 124, 125, 128

Offset: 1

Antti Karttunen, Feb 11 2003

nonn

It appears that a(n) = k such that binomial(prime(k),3) mod 2 = 1. See Maple code. - Gary Detlefs, Dec 06 2011
The above is correct (work mod 4). - Charles R Greathouse IV, Dec 06 2011
The asymptotic density of this sequence is 1/2 (by Dirichlet's theorem). - Amiram Eldar, Mar 01 2021

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

Almost complement of A080147 (1 is excluded from both).

Cf. A000040, A002145, A049084.

pos_of_primes_k_mod_n(300,3,4); # Given in A080147.
A080148 := proc(n)
        numtheory[pi](A002145(n)) ;
end proc:
seq(A080148(n),n=1..40) ; # R. J. Mathar, Dec 08 2011

Flatten[Position[Prime[Range[200]],?(IntegerQ[(#-3)/4]&)]] (* _Harvey P. Dale, Jun 06 2011 *)
Select[Range[135], Mod[Prime[#], 4] == 3 &] (* Amiram Eldar, Mar 01 2021 *)

i=0;forprime(p=2,1e3,i++;if(p%4==3,print1(i", "))) \\ Charles R Greathouse IV, Dec 06 2011

a(n) = A049084(A002145(n)). - R. J. Mathar, Oct 06 2008

A088190 Largest quadratic residue modulo prime(n).

Original entry on oeis.org

1, 1, 4, 4, 9, 12, 16, 17, 18, 28, 28, 36, 40, 41, 42, 52, 57, 60, 65, 64, 72, 76, 81, 88, 96, 100, 100, 105, 108, 112, 124, 129, 136, 137, 148, 148, 156, 161, 162, 172, 177, 180, 184, 192, 196, 196, 209, 220, 225, 228, 232, 232, 240, 249, 256, 258, 268, 268, 276

Offset: 1

Ferenc Adorjan (fadorjan(AT)freemail.hu), Sep 22 2003

nonn

Denote a(n) by LQR(p_n). Observations (tested up to 20000 primes): - the sequence of largest QR modulo the primes (LQR(p_n) is 'almost' monotonic, - p_n-LQR(p_n) is either 1 or a prime value (see A088192) - if LQR(p_n)<=LQR(p_{n-1}) then p_n==7 mod 8 (when n>2) (see A088194) - if LQR(p_n)<=LQR(p_{n-1}) then p_n-LQR(p_n) is an odd prime, but never 5 (see A088195) For a similar set of sequences, related to quadratic non-residues, see A088196-A088201.
From Robert Israel, Oct 31 2024: (Start)
a(n) = prime(n)-1 if and only if n is 1 or in A080147.
a(n) = prime(n)-2 if and only if prime(n) is in A007520.
a(n) = prime(n)-3 if and only if prime(n) is in A107006. (End)

Robert Israel, Table of n, a(n) for n = 1..10000
F. Adorjan, The sequence of largest quadratic residues modulo the primes.

Cf. A007520, A080147, A088191, A088192, A088193, A088194, A088195, A088196, A088197, A088198, A088199, A088200, A088201, A107006.

lqr:= proc(p) local k;
  for k from p-1 by -1 do if numtheory:-quadres(k,p) = 1 then return k fi od:
end proc:
seq(lqr(ithprime(i)),i=1..100); # Robert Israel, Oct 31 2024

a[n_] := With[{p = Prime[n]}, SelectFirst[Range[p - 1, 1, -1], JacobiSymbol[#, p] == 1&]]; Array[a, 100] (* Jean-François Alcover, Feb 16 2018 *)

qrp(fr,to)= {/* Sequence of the largest QR modulo the primes */ local(m,p,v=[]); for(i=fr,to,m=1; p=prime(i); j=2; while((j<=(p-1)/2)&&(m

a(n) = max(r, r==j^2 mod p(n)|j=1, 2, ...(p(n)-1)/2)

A373224 Row sums of A373223.

Original entry on oeis.org

0, 1, 2, 1, 0, 5, 6, 1, 0, 9, 0, 11, 12, 1, 0, 15, 0, 17, 0, -1, 20, -1, -2, 23, 24, 25, 0, -1, 28, 29, 0, -1, 32, -1, 34, -1, 36, -1, -2, 39, -2, 41, -2, 43, 44, -1, -2, -3, -4, 49, 50, -3, 52, -3, 54, -3, 56, -3, 58, 59, -2, 61, -2, -3, 64, 65, -2, 67, -2, 69, 70, -1, -2

Offset: 1

Peter Luschny, May 28 2024

sign

Cf. A373223, A373225, A002144, A080147.

A373224 := n -> local k; add(A373223(n, k), k = 1..n):
lprint(seq(A373224(n), n  = 1..73));

KP(p,q) = kronecker(p,q);
T(n,k) =  my(p=prime(n), q=prime(k)); KP(p,q) * KP(q,p);
a(n) = vecsum(vector(n, k, T(n,k))); \\ Michel Marcus, May 30 2024

a(k) = k - 1 <==> k = 1 or 2 or k term of A080147. In other words: If we index the primes starting at 0 then 0, 1 and the indices of the Pythagorean primes (A002144) are the fixed points of this map.

A170821 Let p = n-th prime; a(n) = smallest k >= 0 such that 4k == 3 mod p.

Original entry on oeis.org

0, 2, 6, 9, 4, 5, 15, 18, 8, 24, 10, 11, 33, 36, 14, 45, 16, 51, 54, 19, 60, 63, 23, 25, 26, 78, 81, 28, 29, 96, 99, 35, 105, 38, 114, 40, 123, 126, 44, 135, 46, 144, 49, 50, 150, 159, 168, 171, 58, 59, 180, 61, 189, 65, 198, 68, 204, 70, 71, 213, 74, 231, 234, 79, 80, 249, 85, 261

Offset: 2

N. J. A. Sloane, Dec 24 2009

Robert Israel, Table of n, a(n) for n = 2..10000
I. Anderson and D. A. Preece, Combinatorially fruitful properties of 3*2^(-1) and 3*2^(-2) modulo p, Discr. Math., 310 (2010), 312-324.

Cf. A000040, A080147, A080148.

f:=proc(n) local b; for b from 0 to n-1 do if 4*b mod n = 3 then RETURN(b); fi; od: -1; end; [seq(f(ithprime(n)),n=2..100)]; # Gives wrong answer for n=2.
# Alternative:
f:= n -> 3/4 mod ithprime(n):
map(f, [$2..100]); # Robert Israel, Dec 03 2018

a[n_] := If[n<3, 0, Module[{p=Prime[n], k=0}, While[Mod[4k, p] != 3, k++]; k]]; Array[a, 100,2] (* Amiram Eldar, Dec 03 2018 *)

a(n) = my(p=prime(n), k=0); while(Mod(4*k, p) != 3, k++); k; \\ Michel Marcus, Dec 03 2018

a(n) = (prime(n)+3)/4 if n is in A080147, (3*prime(n)+3)/4 if n is in A080148 (except for n=2). - Robert Israel, Dec 03 2018

A269703 Numbers k such that prime(k) == 1 (mod 7).

Original entry on oeis.org

10, 14, 20, 30, 31, 45, 47, 52, 60, 68, 75, 82, 87, 90, 94, 101, 113, 115, 120, 122, 126, 132, 134, 144, 153, 156, 162, 163, 169, 177, 183, 192, 209, 213, 220, 226, 233, 239, 250, 251, 262, 267, 269, 288, 295, 304, 306, 315, 320, 324, 330, 337, 342, 344, 346

Offset: 1

Vincenzo Librandi, Mar 04 2016

nonn

The asymptotic density of this sequence is 1/6 (by Dirichlet's theorem). - Amiram Eldar, Mar 01 2021

			a(1) = 10 because prime(10) = 29 and 29 == 1 (mod 7).

The associated primes are in A004619.

Sequences of numbers n such that prime(n) == 1 (mod k): A091178 (k=3,6), A080147 (k=4), A049511 (k=5,10), this sequence (k=7), A269704 (k=8), A269705 (k=9).

[n: n in [1..500] | NthPrime(n) mod 7 eq 1];

Select[Range[500], Mod[Prime[#], 7] == 1 &]

lista(nn) = for(n=1, nn, if(Mod(prime(n),7)==1, print1(n, ", "))); \\ Altug Alkan, Mar 04 2016

a(n) ~ 6*n. - Charles R Greathouse IV, Sep 20 2016 [Corrected by Amiram Eldar, Mar 01 2021]

cp's OEIS Frontend

A267097 a(n) = number of 4k+1 primes among first n primes; least monotonic left inverse of A080147.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A267107 "Chebyshev's bat permutation": a(1) = 1, a(A080147(n)) = A080148(a(n)), a(A080148(n)) = A080147(a(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

Extensions

A267100 Self-inverse permutation of natural numbers: a(1) = 1, a(A080147(n)) = A080148(n), a(A080148(n)) = A080147(n).

Views

Author

Keywords

Links

Crossrefs

Formula

A267105 Permutation of natural numbers: a(1) = 1, a(A080147(n)) = 1+(2*a(n)), a(A080148(n)) = 2*a(n).

Views

Author

Keywords

Links

Crossrefs

Formula

A267106 Permutation of natural numbers: a(1) = 1, a(2n) = A080148(a(n)), a(2n+1) = A080147(a(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A080148 Positions of primes of the form 4*k+3 (A002145) among all primes (A000040).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A088190 Largest quadratic residue modulo prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A373224 Row sums of A373223.

Views

Author

Keywords

Crossrefs

Programs

Maple

PARI

Formula

A170821 Let p = n-th prime; a(n) = smallest k >= 0 such that 4k == 3 mod p.

Views

A267105 Permutation of natural numbers: a(1) = 1, a(A080147(n)) = 1+(2a(n)), a(A080148(n)) = 2a(n).