ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hits 1 - 2 | 2 hits

Sorting

Electronic Resource

Sieve algorithms for perfect power testing (1993)

Bach, Eric ; Sorenson, Jonathan

Springer

Algorithmica 9 (1993), S. 313-328

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Perfect powers ; Number theoretic algorithms ; Riemann hypothesis ; Newton's method ; Sieve algorithms ; Parallel algorithms ; Average-case analysis

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x k . The usual algorithm to recognize perfect powers computes approximatekth roots fork≤log 2 n, and runs in time O(log3 n log log logn). First we improve this worst-case running time toO(log3 n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC 2 algorithm. Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log2 n). Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log2 n/log2 logn) and a median running time ofO(logn). The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains. We also present computational results indicating that our sieve algorithms perform extremely well in practice.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01228507

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

Electronic Resource

Diastereomerically Pure 3-(Silyloxy)oxetanes by a Selective Paternò-Büchi Reaction (1993)

Bach, Thorsten ; Jödicke, Kai

Weinheim : Wiley-Blackwell

Berichte der deutschen chemischen Gesellschaft 126 (1993), S. 2457-2466

add to mindlist on the mindlist

Details

ISSN: 0009-2940

Keywords: Paternò-Büchi reaction ; Oxetanes ; Diastereoselectivity ; Enol silyl ethers ; Photocycloaddition ; Chemistry ; Inorganic Chemistry

Source: Wiley InterScience Backfile Collection 1832-2000

Topics: Chemistry and Pharmacology

Notes: Diastereomerically pure 3-[(trimethylsilyl)oxy]oxetanes 3 were prepared in moderate to good yields (45-72%) by the Paternò-Büchi reaction of silyl enol ethers 2 with benzaldehyde. The photocycloaddition exhibits a high degree of regio- and diastereoselectivity. The substituents R in the silyl enol ether have been varied [R = Me, Et, iPr, tBu, Ph, CH(OMe)2, CH(OCH2)2, C(OCH2)2Me], and it was found that steric bulk is mainly responsible for enhanced selectivity (diastereoselectivity from 70:30 up to 95:5). The regiochemical control is perfect (regioselectivity 〉95:5) except for silyl enol ether 2a (R = Me) in the case of which a 90:10 ratio of regioisomers was observed. Irradiation of the reaction mixture at lower temperature (-25°C) led to a further improvement of diastereoselectivity. The relative configuration of the products obtained was elucidated both by 1H-NMR spectroscopy and by chemical degradation. As a mechanistic hypothesis to explain the high observed diastereoselectivity we propose that the steric environment in the intermediate diradical 11 determines the selectivity according to two possible reaction pathways, i.e. bond formation and retrocleavage.

Additional Material: 3 Ill.