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

Secondary Metabolites by Chemical Screening, 22. Gabosines, New Carba-sugars From Streptomyces (1993)

Bach, Gabriela ; Breiding-Mack, Sabine ; Grabley, Susanne ; [et al.]

Weinheim : Wiley-Blackwell

Liebigs Annalen 1993 (1993), S. 241-250

add to mindlist on the mindlist

Details

ISSN: 0170-2041

Keywords: Gabosine ; Metabolites, secondary ; Streptomyces ; Carba-sugar ; Chemical screening ; Chemistry ; Organic Chemistry

Source: Wiley InterScience Backfile Collection 1832-2000

Topics: Chemistry and Pharmacology

Notes: Chemical screening of different Streptomycetes strains resulted in the detection, isolation, and structure elucidation of a number of novel carba-sugars. The constitution of these secondary metabolites, named gabosines A to K (1 to 11), was deduced from spectroscopic data as well as chemical transformation reactions. The gabosines exhibit a basic C7 skeleton and can be characterized as hydroxylated branched cyclohexanone derivatives, which show structural similarities to carbohydrates deriving from secondary metabolism. The configuration fo the gabosines (absolute stereochemistry for 1, 4, 5, and 6; relative configuration for the remaining metabolites) was determined by derivatization with chiral acids (Helmchen's method), NMR spectral analysis, as well as by a comparison of optical rotation values with those of the already known gabosines B (2) and C (3). The new term “ketocarbasugars” is used to characterize a typical ketone containing subgroup of carba-sugars originating from microbial sources. The well available natural gabosines can be used as suitable chiral building blocks.

Additional Material: 4 Tab.