Masahiko Shin - cp's OEIS frontend

A351914 Numbers m such that the average of the prime numbers up to m is greater than or equal to m/2.

2, 3, 4, 5, 6, 7, 8, 11, 13, 19

Offset: 1

Masahiko Shin, Feb 25 2022

The average of the prime numbers up to m is asymptotically equal to m/2 by the prime number theorem. It is shown by Mandl's inequality that m/2 is strictly greater than the average if m > 19 and thus the sequence is complete.

			5 is a term since the average of the primes up to 5 is (2 + 3 + 5)/3 = 10/3, which is greater than 5/2.
8 is a term since the average of the primes up to 8 is (2 + 3 + 5 + 7)/4 = 17/4 = 4.25, which is greater than 8/2 = 4.

Hassani Mehdi, A Refinement of Mandl's Inequality, report collection, 8 (2) (2005).
Eric Bach and Jefrey Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, Section 2.7, Cambridge, MA: MIT Press, 1996.
Math Stackexchange, Is the average of primes up to n smaller than n/2, if n>19?
Matt Visser, On the arithmetic average of the first n primes, arXiv:2505.04951 [math.NT], 2025. See p. 3.

Cf. A000040, A000720, A034387.

s:= proc(n) s(n):= `if`(n=0, 0, `if`(isprime(n), n, 0)+s(n-1)) end:
q:= n-> is(2*s(n)/numtheory[pi](n)>=n):
select(q, [$2..20])[];  # Alois P. Heinz, Feb 25 2022

s[n_] := s[n] = If[n == 0, 0, If[PrimeQ[n], n, 0] + s[n-1]];
Select[Range[2, 20], 2 s[#]/PrimePi[#] > #&] (* Jean-François Alcover, Dec 26 2022, after Alois P. Heinz *)

from sympy import primerange
def average_of_primes_up_to(i):
    primes_up_to_i =  list(primerange(2, i+1))
    return sum(primes_up_to_i) / len(primes_up_to_i)
def a_list():
    return [i for i in range(2, 20) if average_of_primes_up_to(i) >= i / 2]

2*A034387(a(n))/A000720(a(n)) >= a(n).

A294269 a(n) is the smallest number not already in the sequence which shares a factor with an even number of preceding terms; a(1) = 1.

Original entry on oeis.org

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

Offset: 1

Masahiko Shin, Feb 11 2018

			6 is in the sequence because there are even number of terms (i.e., a(2) = 2, a(3) = 3) which are not coprime to 6 and it is the smallest such number not already in the sequence.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Cf. A005117 (when coprimality condition is changed to divisibility and "even number of terms" is replaced by odd).

R:= [1]:
Cands:= [$2..200]:
for n from 2 to 100 do
  found:= false;
  for i from 1 to nops(Cands) do
    x:= Cands[i];
    if nops(select(t -> igcd(t,x) > 1, R))::even then
       R:= [op(R),x];
       Cands:= subsop(i=NULL,Cands);
       found:= true;
       break
    fi
  od;
  if not found then break fi;
od:
R; # Robert Israel, Apr 15 2024

With[{nn = 66}, Nest[Function[a, Append[a, SelectFirst[Range[Min@ a + 1, Min@ a + 2 nn], Function[k, And[FreeQ[a, k], Mod[Count[a, ?(CoprimeQ[#, k] &)], 2] == Mod[Length@ a, 2]]]]]], {1}, nn]] (* _Michael De Vlieger, Feb 20 2018 *)

findnext(va, nb) = {ok = 0; x = 1; vao = vecsort(va); while (!ok, if (! vecsearch(vao, x) && !(sum(k=1, nb-1, gcd(x, va[k])!=1) % 2), ok = 1, x++);); return (x);}
lista(nn) = {va = [1]; for (n=2, nn, new = findnext(va, n); va = concat(va, new);); va;} \\ Michel Marcus, Mar 29 2018

from math import gcd
def getSeq(n):
    if n == 1:
        return [1]
    prev = getSeq(n-1)
    cand = 1
    while True:
        cand += 1
        if cand in prev:
            continue
        if len([n for n in prev if gcd(cand, n) > 1]) % 2 == 0:
            prev.append(cand)
            return prev
print(getSeq(100))

From Robert Israel, Apr 15 2024: (Start)
G.f.: -1 + 2 * x + (2 - 2 * x + 3 * x^2 + 2 * x^3 - x^4)/(1 - x - x^4 + x^5).
a(n) = a(n - 1) + a(n - 4) - a(n - 5) for n >= 8.
(End)

A295425 a(n) = smallest number > a(n-1) such that the number of preceding terms in the sequence dividing a(n) is divisible by 4; a(1) = 2.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 210, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 330, 331

Offset: 1

Masahiko Shin, Feb 12 2018

First differs from A000040 at a(47)=210.

			3 is in the sequence because no preceding terms (i.e., 0 terms) divide it and 0 is divisible by 4.
4 is not in the sequence because there is only 1 term (i.e., a(1) = 2) that divides it and 1 is not divisible by 4.

Subsequence of A005117.

Cf. A000040, A030059.

With[{k = 4}, Nest[Append[#, SelectFirst[Range[#[[-1]] + 1, #[[-1]] + 120], Function[n, Divisible[Count[#, ?(Divisible[n, #] &)], k]]]] &, {2}, 68]] (* _Michael De Vlieger, Feb 15 2018 *)

isok(k, va, nb) = (sum(j=1, nb, !(k % va[j])) % 4) == 0;
lista(nn) = {va = vector(nn); va[1] = 2; for (n=2, nn, k = va[n-1]+1; while (! isok(k, va, n-1), k++); va[n] = k;); va;} \\ Michel Marcus, Mar 01 2018

import math
def getSeq(n):
    if n == 1:
        return [2]
    prev = getSeq(n-1)
    cand = max(prev)
    while True:
        cand += 1
        if len( [n for n in prev if cand % n == 0] ) % 4 == 0:
            prev.append(cand)
            return prev
print(getSeq(100))

A160504 a(n) = number of ordered pairs (i,j) such that a(i)+a(j)

Original entry on oeis.org

1, 1, 1, 3, 6, 6, 6, 15, 15, 18, 18, 18, 21, 21, 21, 21, 27, 27, 29, 38, 38, 47, 59, 59, 72, 72, 72, 84, 90, 90, 96, 96, 97, 109, 109, 112, 123, 123, 123, 141, 141, 143, 153, 153, 161, 167, 167, 170, 181, 181, 186, 186, 186, 193, 194, 194, 202, 202, 202, 210, 216, 216

Offset: 1

Masahiko Shin, May 16 2009

nonn

It appears that the longest run of identical values in the sequence has length five, occurring twice: a(69) = ... = a(73) = 239 and a(81) = ... = a(85) = 282. Length four appears once at a(13) = ... = a(16) = 21. The last adjacent pair with equal values appears to be a(340) = a(341) = 2558; checked through n=1000. - Hartmut F. W. Hoft, Jun 04 2017

			a(3) = 1 because there is only one possible pair of previous terms, {1, 1}, and its sum is 2, which is less than 3.
a(4) = 3 because there are three possible pairs of previous terms {a(1), a(2)}, {a(1), a(3)}, {a(2), a(3)}, which are here considered distinct even though they all work out to {1, 1} with a sum of 2, which is less than 4.
a(5) = 6 because there are six possible pairs of previous terms: {a(1), a(2)}, {a(1), a(3)}, {a(1), 3}, {a(2), a(3)}, {a(2), 3}, {a(3), 3}, with sums 2, 2, 4, 2, 4, 4, respectively, all of which are less than 6.

Vincenzo Librandi, Table of n, a(n) for n = 1..402

count[cL_] := Module[{n=Length[cL]+1, c=0, i, j}, Do[If[cL[[i]]+cL[[j]]Hartmut F. W. Hoft, Jun 04 2017 *)

There were non-ASCII characters in the definition, which I hope I have interpreted correctly! - N. J. A. Sloane, Jul 23 2009
Definition corrected by Sean A. Irvine, Apr 08 2010
Corrected and extended by Sean A. Irvine, Apr 08 2010

A160505 a(1)=1, a(n) = p*a(n-1), where p is the smallest prime satisfying gcd(n,p)=1.

Original entry on oeis.org

1, 3, 6, 18, 36, 180, 360, 1080, 2160, 6480, 12960, 64800, 129600, 388800, 777600, 2332800, 4665600, 23328000, 46656000, 139968000, 279936000, 839808000, 1679616000, 8398080000, 16796160000, 50388480000, 100776960000

Offset: 1

Masahiko Shin, May 16 2009

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A053669.

A053669 := proc(n) local i,p ; for i from 1 do p := ithprime(i) ; if igcd(n,p) = 1 then return p; end if; end do: end proc:
A160505 := proc(n) option remember; if n = 1 then 1; else procname(n-1)*A053669(n) ; end if; end proc: # R. J. Mathar, Jul 06 2011

sp[{n_,a_}]:=Module[{p=2},While[GCD[n+1,p]!=1,p=NextPrime[p]];{n+1,a*p}]; NestList[sp,{1,1},30][[All,2]] (* Harvey P. Dale, May 08 2021 *)

A160453 Numbers k which have a prime divisor p such that 1 is the only positive integer which divides k/p^m and is congruent to 1 modulo p, where p^(m+1) does not divide k.

Original entry on oeis.org

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

Offset: 1

Masahiko Shin, May 14 2009

nonn

The solvability of a group whose order is a(n) can be reduced to the solvability of smaller group using the Sylow theorems, provided the order is not a prime.

80 is not a member of this sequence, but is a member of A168186. - Franklin T. Adams-Watters, Jan 26 2010

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

All three of A023805, A160453, A168186 are different.

is(k)=if(k<12,return(k>0));my(f=factor(k)); for(i=1,#f~, fordiv(k/f[i,1]^f[i,2],d, if(d>1&&d%f[i,1]==1,next(2))); return(1)); 0 \\ Charles R Greathouse IV, Oct 27 2013

Corrected by Charles R Greathouse IV, Oct 27 2013

A135280 Numbers n of the form n = (x^2+1)(y^2+1), x,y > 0.

Original entry on oeis.org

4, 10, 20, 25, 34, 50, 52, 74, 85, 100, 130, 164, 170, 185, 202, 244, 250, 260, 289, 290, 325, 340, 370, 394, 410, 442, 452, 500, 505, 514, 580, 610, 629, 650, 676, 724, 725, 802, 820, 850, 884, 962, 970, 985, 1010, 1060, 1105, 1130, 1154, 1220, 1252, 1285

Offset: 1

Masahiko Shin, Dec 02 2007

			The associated (x^2,y^2)-tuples are (1,1), (1,4), (1,9), (4,4), (1,16), (4,9), (1,25), (1,36), (4,16), (1,49) etc., producing 2*2=4, 2*5=10, 2*10=20, 5*5=25 etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A002808, which has form (x+1)(y+1), x, y > 0.

isA135280 := proc(n) local d ; for d in numtheory[divisors](n) do if d > 1 and n/d > 1 then if issqr(d-1) and issqr(n/d-1) then RETURN(true) ; fi ; fi ; od: RETURN(false) ; end: for n from 4 to 800 do if isA135280(n) then printf("%d, ",n) ; fi ; od: # R. J. Mathar, Dec 12 2007

Take[Union[(#[[1]]^2+1)(#[[2]]^2+1)&/@Tuples[Range[30],2]],60] (* Harvey P. Dale, Feb 15 2012 *)

list(lim)=my(v=List(),t,X);for(x=1,sqrtint(lim\2-1),X=x^2+1; for(y=1,min(sqrtint(lim\X-1),x),listput(v,X*y^2+X))); vecsort(Vec(v),,8) \\ Charles R Greathouse IV, Oct 27 2013

Corrected and extended by Stefan Steinerberger and R. J. Mathar, Dec 05 2007

A133482 a(p_1^e_1p_2^e_2.....p_m^e_m) = (p_1^p_1)^e_1(p_2^p^2)^e_2.....(p_m^p_m)^e_m where p_1^e_1p_2^e_2.....*p_m^e_m is the prime decomposition of n.

Original entry on oeis.org

1, 4, 27, 16, 3125, 108, 823543, 64, 729, 12500, 285311670611, 432, 302875106592253, 3294172, 84375, 256, 827240261886336764177, 2916, 1978419655660313589123979, 50000, 22235661, 1141246682444, 20880467999847912034355032910567, 1728, 9765625, 1211500426369012, 19683, 13176688, 2567686153161211134561828214731016126483469, 337500

Offset: 1

Masahiko Shin, Nov 29 2007

Totally multiplicative sequence with a(p) = p^p for prime p. - Jaroslav Krizek, Oct 17 2009

Sum_{n>=1} 1/a(n) = Product_{p prime} (1 + 1/(p^p - 1)) = 1.3850602852044891763... - Amiram Eldar, Dec 08 2020

			a(6) = a(2^1*3^1) = 2^2^1*3^3^1 = 4*27 = 108.

Amiram Eldar, Table of n, a(n) for n = 1..388

A133482 := proc(n) local ifs,f ; if n = 1 then 1; else ifs := ifactors(n)[2] ; mul( (op(1,f)^op(1,f))^op(2,f), f=ifs) ; fi ; end: seq(A133482(n),n=1..30) ; # R. J. Mathar, Nov 30 2007

f[p_, e_] := (p^(p*e)); a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 30] (* Amiram Eldar, Dec 08 2020 *)

Multiplicative with a(p^e) = p^(pe). If n = Product p(k)^e(k) then a(n) = Product p(k)^(p(k)*e(k)). - Jaroslav Krizek, Oct 17 2009

Corrected and extended by R. J. Mathar, Nov 30 2007

A133457 Irregular triangle read by rows: row n gives exponents in expression for n as a sum of powers of 2.

Original entry on oeis.org

0, 1, 0, 1, 2, 0, 2, 1, 2, 0, 1, 2, 3, 0, 3, 1, 3, 0, 1, 3, 2, 3, 0, 2, 3, 1, 2, 3, 0, 1, 2, 3, 4, 0, 4, 1, 4, 0, 1, 4, 2, 4, 0, 2, 4, 1, 2, 4, 0, 1, 2, 4, 3, 4, 0, 3, 4, 1, 3, 4, 0, 1, 3, 4, 2, 3, 4, 0, 2, 3, 4, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 5, 1, 5, 0, 1, 5, 2, 5, 0, 2, 5, 1, 2, 5, 0, 1, 2, 5, 3, 5, 0, 3, 5

Offset: 1

Masahiko Shin, Nov 27 2007

This sequence contains every increasing finite sequence. For example, the finite sequence {0,2,3,5} arises from n = 45.
Essentially A030308(n,k)*k, then entries removed where A030308(n,k)=0. - R. J. Mathar, Nov 30 2007
In the corresponding irregular triangle {a(n)+1}, the m-th row gives all positive integer roots m_i of polynomial {m,k}. - see link [Shevelev]; see also A264613. - Vladimir Shevelev, Dec 13 2015

			1 = 2^0.
2 = 2^1.
3 = 2^0 + 2^1.
4 = 2^2.
5 = 2^0 + 2^2.
etc. and reading the exponents gives the rows of the triangle.

Reinhard Zumkeller, Rows n = 1..1024 of triangle, flattened
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)

Cf. A003071, A030308, A048793, A067255, A264613.

Cf. A073642 (row sums), A272011 (rows reversed).

a133457 n k = a133457_tabf !! (n-1) !! n
a133457_row n = a133457_tabf !! (n-1)
a133457_tabf = map (fst . unzip . filter ((> 0) . snd) . zip [0..]) $
                   tail a030308_tabf
-- Reinhard Zumkeller, Oct 28 2013, Feb 06 2013

A133457 := proc(n) local a,bdigs,i ; a := [] ; bdigs := convert(n,base,2) ; for i from 1 to nops(bdigs) do if op(i,bdigs) <> 0 then a := [op(a),i-1] ; fi ; od: a ; end: seq(op(A133457(n)),n=1..80) ; # R. J. Mathar, Nov 30 2007

Array[Join @@ Position[#, 1] - 1 &@ Reverse@ IntegerDigits[#, 2] &, 41] // Flatten (* Michael De Vlieger, Oct 08 2017 *)

a(n) = A048793(n) - 1.

More terms from R. J. Mathar, Nov 30 2007

A135282 Largest k such that 2^k appears in the trajectory of the Collatz 3x+1 sequence started at n.

Original entry on oeis.org

0, 1, 4, 2, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 4, 4, 4, 4, 4, 4, 4, 4, 6, 8, 4, 4

Offset: 1

Masahiko Shin, Dec 02 2007

nonn

Most of the first eighty terms in the sequence are 4, because the trajectories finish with 16 -> 8 -> 4 -> 2 -> 1. - R. J. Mathar, Dec 12 2007
Most of the first ten thousand terms are 4, and there only appear 4, 6, 8, and 10 in the extent, unless n is power of 2. In the other words, it seems that the trajectory of the Collatz 3x + 1 sequence ends with either 16, 64, 256 or 1024. There are few exceptional terms, for example a(10920) = 12, a(10922) = 14. It also seems all terms are even unless n is an odd power of 2. - Masahiko Shin, Mar 16 2010
It is true that all terms are even unless n is an odd power of 2: 2 == -1 mod 3, 2 * 2 == -1 * -1 == 1 mod 3. Therefore only even-indexed powers of 2 are congruent to 1 mod 3 and thus reachable by either a halving step or a "tripling step," whereas the odd-indexed powers of 2 are only reachable by a halving step or as an initial value. - Alonso del Arte, Aug 15 2010

			a(6) = 4 because the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1; there 16 = 2^4 is the largest power of 2 encountered.

Cf. A007814, A209229, A070165, A232503.

Cf. A006577, A208981.

#include  int main(){ int i, s, f; for(i = 2; i < 10000; i++){ f = 0; s = i; while(s != 1){ if(s % 2 == 0){ s = s/2; f++;} else{ f = 0; s = 3 * s + 1; } } printf("%d,", f); } return 0; } /* Masahiko Shin, Mar 16 2010 */

a135282 = a007814 . head . filter ((== 1) . a209229) . a070165_row
-- Reinhard Zumkeller, Jan 02 2013

A135282 := proc(n) local k,threen1 ; k := 0 : threen1 := n ; while threen1 > 1 do if 2^ilog[2](threen1) = threen1 then k := max(k,ilog[2](threen1)) ; fi ; if threen1 mod 2 = 0 then threen1 := threen1/2 ; else threen1 := 3*threen1+1 ; fi ; od: RETURN(k) ; end: for n from 1 to 80 do printf("%d, ",A135282(n)) ; od: # R. J. Mathar, Dec 12 2007

Collatz[n_] := If[EvenQ[n], n/2, 3*n + 1]; Log[2, Table[NestWhile[Collatz, n, ! IntegerQ[Log[2, #]] &], {n, 100}]] (* T. D. Noe, Mar 05 2012 *)

a(n) = A006577(n) - A208981(n) (after Alonso del Arte's comment in A208981), if A006577(n) is not -1. - Omar E. Pol, Apr 10 2022

Edited and extended by R. J. Mathar, Dec 12 2007

More terms from Masahiko Shin, Mar 16 2010

cp's OEIS Frontend

User: Masahiko Shin

A351914 Numbers m such that the average of the prime numbers up to m is greater than or equal to m/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A294269 a(n) is the smallest number not already in the sequence which shares a factor with an even number of preceding terms; a(1) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A295425 a(n) = smallest number > a(n-1) such that the number of preceding terms in the sequence dividing a(n) is divisible by 4; a(1) = 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

A160504 a(n) = number of ordered pairs (i,j) such that a(i)+a(j)

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Extensions

A160505 a(1)=1, a(n) = p*a(n-1), where p is the smallest prime satisfying gcd(n,p)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A160453 Numbers k which have a prime divisor p such that 1 is the only positive integer which divides k/p^m and is congruent to 1 modulo p, where p^(m+1) does not divide k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A135280 Numbers n of the form n = (x^2+1)(y^2+1), x,y > 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A133482 a(p_1^e_1p_2^e_2.....p_m^e_m) = (p_1^p_1)^e_1(p_2^p^2)^e_2.....(p_m^p_m)^e_m where p_1^e_1p_2^e_2.....*p_m^e_m is the prime decomposition of n.