login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A198512 Half the difference between an odd squarefree semiprime's factors. 0
1, 2, 4, 1, 5, 7, 3, 8, 4, 10, 2, 6, 13, 3, 14, 7, 17, 9, 5, 19, 20, 6, 22, 1, 12, 13, 25, 8, 28, 29, 16, 3, 32, 11, 18, 4, 34, 19, 12, 35, 2, 21, 38, 3, 40, 6, 15, 24, 43, 17, 47, 27, 5, 18, 28, 9, 1, 20, 31, 10 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

It is trivially easy to factor small semiprimes, even with trial division. But larger semiprimes can pose quite a challenge. Behrends (2008) gives a method cryptanalysts can use to factor a large semiprime that can work reasonably well if the prime factors, even if also very large, can be figured out if they are not spaced too far apart. The method exploits the following fact about odd semiprimes:

The square of half the difference between the prime factors, when added to the semiprime, gives a perfect square. The square root of that perfect square is halfway between the two prime factors of the semiprime. For example: 39 = 3 * 13, 13 - 3 = 10, 10/2 = 5, 39 + 5^2 = 64, sqrt(64) = 8, and lastly 8 - 5 = 3 and 8 + 5 = 13.

The method then is to add perfect squares to a suspected semiprime until finding another perfect square. In turn, cryptographers should choose large semiprimes with widely distant prime factors.

REFERENCES

Ehrhard Behrends, Five-Minute Mathematics, translated by David Kramer. American Mathematical Society (2008) p.s 25-26

LINKS

Table of n, a(n) for n=1..60.

EXAMPLE

a(2) = 2 because the second odd squarefree semiprime is 21 and its two factors (3 and 7) are 4 apart, and 4/2 = 2

a(3) = 4 because the third odd squarefree semiprime is 33 and its two factors (3 and 11) are 8 apart, and 8/2 = 4

MATHEMATICA

(* First run the program for A046388 *) Table[(FactorInteger[A046388[[n]]][[2, 1]] - FactorInteger[A046388[[n]]][[1, 1]])/2, {n, 60}]

CROSSREFS

Cf. A046388.

Sequence in context: A278437 A175036 A177985 * A059573 A308437 A201283

Adjacent sequences: A198509 A198510 A198511 * A198513 A198514 A198515

KEYWORD

nonn,easy

AUTHOR

Alonso del Arte, Oct 25 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 28 20:13 EST 2022. Contains 358421 sequences. (Running on oeis4.)