A167181 -id:A167181 - cp's OEIS frontend

A016105 Blum integers: numbers of the form p * q where p and q are distinct primes congruent to 3 (mod 4).

21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, 501, 517, 537, 553, 573, 581, 589, 597, 633, 649, 669, 681, 713, 717, 721, 737, 749, 753, 781, 789

Offset: 1

Robert G. Wilson v

Subsequence of A084109. - Ralf Stephan and David W. Wilson, Apr 17 2005
Subsequence of A046388. - Altug Alkan, Dec 10 2015
Subsequence of A339817. No common terms with A339870. - Antti Karttunen, Dec 26 2020
Named after the Venezuelan-American computer scientist Manuel Blum (b. 1938). - Amiram Eldar, Jun 06 2021
First introduced by Blum, Blum, & Shub for the generation of pseudorandom numbers and later applied (by Manuel Blum and other authors) to zero-knowledge proofs. - Charles R Greathouse IV, Sep 26 2024

Lenore Blum, Manuel Blum, and Mike Shub. A simple unpredictable pseudorandom number generator, SIAM Journal on computing 15:2 (1986), pp. 364-383.

Antti Karttunen, Table of n, a(n) for n = 1..26828 (all terms < 2^19; first 1000 terms from T. D. Noe)
Joe Hurd, Blum Integers, Talk at the Trinity College, Jan 20 1997.
Wikipedia, Blum integer.

Cf. A002145, A006881, A046388, A339870.
Intersection of A005117 and A107978.
Also, subsequence of the following sequences: A046388, A084109, A091113, A167181, A339817.

import Data.Set (singleton, fromList, deleteFindMin, union)
a016105 n = a016105_list !! (n-1)
a016105_list = f [3,7] (drop 2 a002145_list) 21 (singleton 21) where
   f qs (p:p':ps) t s
     | m < t     = m : f qs (p:p':ps) t s'
     | otherwise = m : f (p:qs) (p':ps) t' (s' `union` (fromList pqs))
     where (m,s') = deleteFindMin s
           t' = head $ dropWhile (> 3*p') pqs
           pqs = map (p *) qs
-- Reinhard Zumkeller, Sep 23 2011

N:= 10000: # to get all terms <= N
Primes:= select(isprime, [seq(i,i=3..N/3,4)]):
S:=select(`<=`,{seq(seq(Primes[i]*Primes[j],i=1..j-1),j=2..nops(Primes))},N):
sort(convert(S,list)); # Robert Israel, Dec 11 2015

With[{upto = 820}, Select[Union[Times@@@Subsets[ Select[Prime[Range[ PrimePi[ NextPrime[upto/3]]]], Mod[#, 4] == 3 &], {2}]], # <= upto &]] (* Harvey P. Dale, Aug 19 2011 *)
Select[4Range[5, 197] + 1, PrimeNu[#] == 2 && MoebiusMu[#] == 1 && Mod[FactorInteger[#][[1, 1]], 4] != 1 &] (* Alonso del Arte, Nov 18 2015 *)

list(lim)=my(P=List(),v=List(),t,p); forprimestep(p=3,lim\3,4, listput(P,p)); for(i=2,#P, p=P[i]; for(j=1,i-1, t=p*P[j]; if(t>lim, break); listput(v,t))); Set(v) \\ Charles R Greathouse IV, Jul 01 2016, updated Sep 26 2024

isA016105(n) = (2==omega(n)&&2==bigomega(n)&&1==(n%4)&&3==((factor(n)[1,1])%4)); \\ Antti Karttunen, Dec 26 2020

use ntheory ":all"; forcomposites { say if ($ % 4) == 1 && is_square_free($) && scalar(factor($)) == 2 && !scalar(grep { ($ % 4) != 3 } factor($)); } 10000; # _Dana Jacobsen, Dec 10 2015

from sympy import factorint
def ok(n):
    fn = factorint(n)
    return len(fn) == sum(fn.values()) == 2 and all(f%4 == 3 for f in fn)
print([k for k in range(790) if ok(k)]) # Michael S. Branicky, Dec 20 2021

a(n) = A195758(n) * A195759(n). - Reinhard Zumkeller, Sep 23 2011

a(n) ~ 4n log n/log log n. - Charles R Greathouse IV, Sep 17 2022

More terms from Erich Friedman

A339870 Composite numbers k of the form 4u+1 for which the odd part of phi(k) divides k-1.

Original entry on oeis.org

85, 561, 1105, 1261, 1285, 2465, 4369, 6601, 8245, 8481, 9061, 9605, 10585, 16405, 16705, 17733, 18721, 19669, 21845, 23001, 28645, 30889, 38165, 42121, 43165, 46657, 54741, 56797, 57205, 62745, 65365, 74593, 78013, 83665, 88561, 91001, 106141, 117181, 124645, 126701, 134521, 136981, 141661, 162401, 171205, 176437

Offset: 1

Antti Karttunen, Dec 22 2020

nonn

From Antti Karttunen, Dec 26 2020: (Start)
Equally, squarefree composite numbers k of the form 4u+1 for which A336466(k) divides k-1. This follows because on squarefree n, A336466(n) = A053575(n).
No common terms with A016105, because 4xy + 2(x+y) + 1 does not divide 4xy + 3(x+y) + 2 for any distinct x, y >= 0 (where 4x+3 and 4y+3 are the two prime factors of Blum integers).
This can also seen by another way: If this sequence contained any Blum integers, then, because A016105 is a subsequence of A339817, we would have found a composite number n satisfying Lehmer's totient problem y * phi(n) = n-1, for some integer y > 1. But Lehmer proved that such solutions should have at least 7 distinct prime factors, while Blum integers have only two.
Moreover, it seems that none of the terms of A167181 may occur here, and a few of A137409 (i.e., of A125667). See A339875 for those terms.
(End)

			85 = 4*21 + 1 = 5*17, thus phi(85) = 4*16 = 64, the odd part of which is A000265(64) = 1, which certainly divides 85-1, therefore 85 is included as a term.
561 = 4*140 + 1 = 3*11*17, thus phi(561) = 2*10*16 = 320, the odd part of which is A000265(320) = 5, which divides 560, therefore 561 is included.

Antti Karttunen, Table of n, a(n) for n = 1..1316
D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
Wikipedia, Lehmer's totient problem

Cf. A000010, A000265, A016105, A053575, A137409, A167181, A336466.
Subsequence of A005117.
Intersection of A091113 and A339880.
Cf. A339875 (a subsequence).
Cf. also comments in A339817.

odd[n_] := n/2^IntegerExponent[n, 2]; Select[4*Range[45000] + 1, CompositeQ[#] && Divisible[# - 1, odd[EulerPhi[#]]] &] (* Amiram Eldar, Feb 17 2021 *)

A000265(n) = (n>>valuation(n, 2));
isA339870(n) = ((n>1)&&!isprime(n)&&(1==(n%4))&&!((n-1)%A000265(eulerphi(n))));

A185321 Carmichael numbers congruent to 3 modulo 4.

Original entry on oeis.org

8911, 1024651, 1152271, 5481451, 10267951, 14913991, 64377991, 67902031, 139952671, 178482151, 368113411, 395044651, 612816751, 652969351, 743404663, 1419339691, 1588247851, 2000436751, 2199931651, 2560600351, 3102234751, 3215031751, 3411338491, 4340265931

Offset: 1

José María Grau Ribas, Jan 27 2012

nonn

Most Carmichael numbers are congruent to 1 modulo 4.
This is a subsequence of A167181: if a prime p | a(n), (p-1) | (a(n)-1) by Korselt's criterion. But a(n)-1 is 2 mod 4, so p-1 cannot be 0 mod 4. Hence all primes dividing a(n) are 3 mod 4. - Charles R Greathouse IV, Jan 27 2012
Pinch call the intersection of A007304 with this sequence C3, which are precisely those numbers which pass a Rabin-Miller test to a random base with probability 1/4. The first member of this sequence not in C3 is a(16) = 7 * 11 * 19 * 103 * 9419. - Charles R Greathouse IV, Jan 27 2012
Wright proves that this sequence is infinite, and in particular there are more than x^(k/(log log log x)^2) terms up to x for some k and large enough x. - Charles R Greathouse IV, Nov 09 2015

Donovan Johnson and Charles R Greathouse IV, Table of n, a(n) for n = 1..15447 (first 6838 terms from Johnson)
Charles R Greathouse IV, GP script to compute terms
Charles R Greathouse IV, Alternate GP script to compute terms
R. G. E. Pinch, The Carmichael numbers up to 10^15, Mathematics of Computation 61:203 (1993), pp. 381-391.
Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bull. London Math. Soc. 45:5 (2013), pp. 943-952.

Subsequence of A002997, A167181 (and hence A004614), A026424, and A177884.

Select[4Range[10^4] + 3, (!PrimeQ[#] && IntegerQ[(# - 1)/CarmichaelLambda[#]]) &]

Korselt(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1
p=5;forprime(q=7,1e7,forstep(n=if(p%4==3,p+4,p+2),q-2,4,if(Korselt(n),print1(n", ")));p=q) \\ Charles R Greathouse IV, Jan 27 2012

a(7)-a(40) from Charles R Greathouse IV, Jan 27 2012

A231754 Products of distinct primes congruent to 1 modulo 4 (A002144).

Original entry on oeis.org

1, 5, 13, 17, 29, 37, 41, 53, 61, 65, 73, 85, 89, 97, 101, 109, 113, 137, 145, 149, 157, 173, 181, 185, 193, 197, 205, 221, 229, 233, 241, 257, 265, 269, 277, 281, 293, 305, 313, 317, 337, 349, 353, 365, 373, 377, 389, 397, 401, 409, 421, 433, 445, 449

Offset: 1

Michel Marcus, Nov 13 2013

Contains A002144 as a subsequence, and is a subsequence of A016813 and of A005117.

Also, these numbers satisfy A231589(n) = floor(n*(n-1)/4) (A011848).

			65 = 5*13 is in the sequence since both 5 and 13 are congruent to 1 modulo 4.

R. J. Mathar, Table of n, a(n) for n = 1..4999
Rafael Jakimczuk, Generalizations of Mertens's Formula and k-Free and s-Full Numbers with Prime Divisors in Arithmetic Progression, ResearchGate, 2024.
Shailesh A. Shirali, A family portrait of primes-a case study in discrimination, Math. Mag., Vol. 70, No. 4 (Oct., 1997), pp. 263-272.

Intersection of A005117 and A004613.
Cf. A002144, A011848, A016813, A167181, A231589.
Cf. A088539, A175647.

isA231754 := proc(n)
    local d;
    for d in ifactors(n)[2] do
        if op(2,d) > 1 then
            return false;
        elif modp(op(1,d),4) <> 1 then
            return false;
        end if;
    end do:
    true ;
end proc:
for n from 1 to 500 do
    if isA231754(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Mar 16 2016

Select[Range[500], # == 1 || AllTrue[FactorInteger[#], Last[#1] == 1 && Mod[First[#1], 4] == 1 &] &] (* Amiram Eldar, Mar 08 2024 *)

isok(n) = if (! issquarefree(n), return (0)); if (n > 1, f = factor(n); for (i=1, #f~, if (f[i, 1] % 4 != 1, return (0)))); 1

The number of terms that do not exceed x is ~ c * x / sqrt(log(x)), where c = A088539 * sqrt(A175647) / Pi = 0.3097281805... (Jakimczuk, 2024, Theorem 3.10, p. 26). - Amiram Eldar, Mar 08 2024

A363340 a(n) is the smallest positive integer such that a(n) * n is the sum of two squares.

Original entry on oeis.org

1, 1, 3, 1, 1, 3, 7, 1, 1, 1, 11, 3, 1, 7, 3, 1, 1, 1, 19, 1, 21, 11, 23, 3, 1, 1, 3, 7, 1, 3, 31, 1, 33, 1, 7, 1, 1, 19, 3, 1, 1, 21, 43, 11, 1, 23, 47, 3, 1, 1, 3, 1, 1, 3, 11, 7, 57, 1, 59, 3, 1, 31, 7, 1, 1, 33, 67, 1, 69, 7, 71, 1, 1, 1, 3, 19, 77, 3, 79

Offset: 1

Peter Schorn, May 28 2023

Using Fermat's two-squares theorem it is easy to see that a(n) is the product of all prime factors of n that are congruent to 3 modulo 4 and have an odd exponent.
This implies that a(n) is also the smallest positive integer such that n / a(n) is the sum of two squares.
Equivalently, a(n) is the product of all primes of the form 4k+3 that divide the squarefree part of n. If we use the squarefree kernel instead, we get A170819. - Peter Munn, Aug 06 2023

			a(1) = a(2) = 1 since 1 and 2 are sums of two squares.
a(3) = 3 since 3 and 6 are not sums of two squares but 3*3 is.
a(6) = 3 since 6 and 12 are not sums of two squares but 3*6 = 3^2 + 3^2.

Cf. A001481 (positions of 1's), A167181 (range of values).
Fixed points: A167181.
Cf. A000265, A002145, A007913, A059897, A097706, A170819.

a(n) = my(r=1); foreach(mattranspose(factor(n)), f, if(f[1]%4==3&&f[2]%2==1, r*=f[1])); r

Multiplicative with a(p^e) = p if p^e == 3 (mod 4), otherwise 1. - Peter Munn, Jul 03 2023
From Peter Munn, Aug 06 2023: (Start)
a(n) = A007913(A097706(n)) = A097706(A007913(n)).
a(n) == A000265(n) (mod 4).
a(A059897(n, k)) = A059897(a(n), a(k)).
(End)

A327122 Expansion of Sum_{k>=1} sigma(k) * x^k / (1 + x^(2*k)), where sigma = A000203.

Original entry on oeis.org

1, 3, 3, 7, 7, 9, 7, 15, 10, 21, 11, 21, 15, 21, 21, 31, 19, 30, 19, 49, 21, 33, 23, 45, 38, 45, 30, 49, 31, 63, 31, 63, 33, 57, 49, 70, 39, 57, 45, 105, 43, 63, 43, 77, 70, 69, 47, 93, 50, 114, 57, 105, 55, 90, 77, 105, 57, 93, 59, 147, 63, 93, 70, 127, 105

Offset: 1

Ilya Gutkovskiy, Sep 14 2019

Inverse Moebius transform of A050469.

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

Cf. A000203, A050469, A101455, A167181 (fixed points), A262209, A288417, A327123.

Cf. A072691, A175647, A243381.

nmax = 65; CoefficientList[Series[Sum[DivisorSigma[1, k] x^k/(1 + x^(2 k)), {k, 1, nmax}], {x, 0, nmax}], x] // Rest
A050469[n_] := DivisorSum[n, # &, MemberQ[{1}, Mod[n/#, 4]] &] - DivisorSum[n, # &, MemberQ[{3}, Mod[n/#, 4]] &]; a[n_] := DivisorSum[n, A050469[#] &]; Table[a[n], {n, 1, 65}]
f[p_, e_] := If[Mod[p, 4] == 1, (p^(e+2)-(e+2)*p+e+1)/(p-1)^2, (2*p^(e+2) + ((-1)^e-1)*p - ((-1)^e+1))/(2*(p^2-1))]; f[2, e_] := 2^(e+1)-1; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 70] (* Amiram Eldar, Aug 28 2023 *)

a(n) = {my(f = factor(n)); prod(i = 1, #f~, p = f[i,1]; e = f[i,2]; if(p == 2, 2^(e+1)-1, if(p%4 == 1, (p^(e+2)-(e+2)*p+e+1)/(p-1)^2, (2*p^(e+2) + ((-1)^e-1)*p - ((-1)^e+1))/(2*(p^2-1))))); } \\ Amiram Eldar, Aug 28 2023

a(n) = Sum_{d|n} A050469(d).
From Amiram Eldar, Aug 28 2023: (Start)
Multiplicative with a(2^e) = 2^(e+1)-1, and if p is an odd prime a(p^e) = (p^(e+2)-(e+2)*p+e+1)/(p-1)^2 if p == 1 (mod 4) and (2*p^(e+2) + ((-1)^e-1)*p - ((-1)^e+1))/(2*(p^2-1)) otherwise.
Sum_{k=1..n} a(k) ~ c * n^2, where c = Pi^2/12 * (A175647/A243381) = 0.753351504961... . (End)

A371014 The number of divisors of n that are the sum of 2 squares.

Original entry on oeis.org

1, 2, 1, 3, 2, 2, 1, 4, 2, 4, 1, 3, 2, 2, 2, 5, 2, 4, 1, 6, 1, 2, 1, 4, 3, 4, 2, 3, 2, 4, 1, 6, 1, 4, 2, 6, 2, 2, 2, 8, 2, 2, 1, 3, 4, 2, 1, 5, 2, 6, 2, 6, 2, 4, 2, 4, 1, 4, 1, 6, 2, 2, 2, 7, 4, 2, 1, 6, 1, 4, 1, 8, 2, 4, 3, 3, 1, 4, 1, 10, 3, 4, 1, 3, 4, 2, 2

Offset: 1

Amiram Eldar, Mar 08 2024

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

Cf. A001481, A004614, A046951, A072437, A167181, A371015.

f[p_, e_] := If[Mod[p, 4] == 3, Floor[e/2] + 1, e + 1]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i, 1]%4 == 3, f[i, 2]\2 + 1, f[i, 2] + 1));}

Multiplicative with a(p^e) = floor(e/2) + 1 if p == 3 (mod 4), and e+1 otherwise.
a(n) = A000005(n) if and only if n is in A072437.
a(n) = A046951(n) if and only if n is in A004614.
a(n) = 1 if and only if n is in A167181.

A371015 The largest divisor of n that is the sum of 2 squares.

Original entry on oeis.org

1, 2, 1, 4, 5, 2, 1, 8, 9, 10, 1, 4, 13, 2, 5, 16, 17, 18, 1, 20, 1, 2, 1, 8, 25, 26, 9, 4, 29, 10, 1, 32, 1, 34, 5, 36, 37, 2, 13, 40, 41, 2, 1, 4, 45, 2, 1, 16, 49, 50, 17, 52, 53, 18, 5, 8, 1, 58, 1, 20, 61, 2, 9, 64, 65, 2, 1, 68, 1, 10, 1, 72, 73, 74, 25

Offset: 1

Amiram Eldar, Mar 08 2024

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

Cf. A001481, A167181, A363340, A371014.

f[p_, e_] := If[Mod[p, 4] == 3, p^(2*Floor[e/2]), p^e]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, f[i, 1]^if(f[i, 1]%4 == 3, 2*(f[i, 2]\2), f[i, 2]));}

Multiplicative with a(p^e) = p^(2*floor(e/2)) if p == 3 (mod 4), and p^e otherwise.
a(n) = n / A363340(n).
a(n) = n if and only if n is in A001481.
a(n) = 1 if and only if n is in A167181.

cp's OEIS Frontend

A016105 Blum integers: numbers of the form p * q where p and q are distinct primes congruent to 3 (mod 4).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Perl

Python

Formula

Extensions

A339870 Composite numbers k of the form 4u+1 for which the odd part of phi(k) divides k-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A185321 Carmichael numbers congruent to 3 modulo 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A231754 Products of distinct primes congruent to 1 modulo 4 (A002144).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A363340 a(n) is the smallest positive integer such that a(n) * n is the sum of two squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A327122 Expansion of Sum_{k>=1} sigma(k) * x^k / (1 + x^(2*k)), where sigma = A000203.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A371014 The number of divisors of n that are the sum of 2 squares.

Views

Author

Keywords

Links