text:
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

# Identification of type of threading dislocation causing reverse leakage in GaN p–n junctions after continuous forward current stress

## Abstract

Power devices are operated under harsh conditions, such as high currents and voltages, and so degradation of these devices is an important issue. Our group previously found significant increases in reverse leakage current after applying continuous forward current stress to GaN p–n junctions. In the present study, we identified the type of threading dislocations that provide pathways for this reverse leakage current. GaN p–n diodes were grown by metalorganic vapor phase epitaxy on freestanding GaN(0001) substrates with threading dislocation densities of approximately 3 × 105 cm−2. These diodes exhibited a breakdown voltage on the order of 200 V and avalanche capability. The leakage current in some diodes in response to a reverse bias was found to rapidly increase with continuous forward current injection, and leakage sites were identified by optical emission microscopy. Closed-core threading screw dislocations (TSDs) were found at five emission spots based on cross-sectional transmission electron microscopy analyses using two-beam diffraction conditions. The Burgers vectors of these dislocations were identified as [0001] using large-angle convergent-beam electron diffraction. Thus, TSDs for which b = 1c are believed to provide current leakage paths in response to forward current stress.

## Introduction

Vertical power devices based on gallium nitride (GaN) have recently been developed1,2,3,4,5,6,7,8 as a means of minimizing power losses in electrical conversion systems requiring high current capabilities, such as automotive applications9,10. This technology is expected to make a significant contribution to future sustainable development initiatives. It is important for electrical systems, especially those used in automotive applications, to be reliable, and the reliability of vertical GaN p–n junctions subjected to high reverse biases, temperatures and current injections has been assessed. Because electric field crowding at device edges significantly lowers the breakdown voltage and can cause irreversible breakdown, various types of edge terminations have been developed and have demonstrated good avalanche capabilities7,8,11,12,13,14,15,16.

In power devices, the reverse leakage current below the breakdown voltage needs be controlled. The previous studies discussed the impacts of the threading dislocations as sources of reverse leakage current, focusing on the initial reverse bias characteristics17,18,19,20,21. Compared with the number of studies regarding the initial reliability of these devices, there have been few reports concerning hold tests under high reverse bias or high current stress22,23,24. Kizilyalli et al.22 subjected p–n diodes on freestanding GaN substrates having threading dislocation densities in the range of 104 to 106 cm−2 to high temperatures and reverse biases and found that the majority of the diodes exhibited a durability of over 1000 h. Our group also demonstrated that GaN p–n junctions with threading dislocation densities less than 104 cm−2 were not degraded even under a high reverse bias corresponding to the avalanche condition at 175 °C over time spans of up to 1 h24. However, in contrast to this highly robust behavior, the reverse leakage current in some diodes rapidly increased after continuous forward current stress was applied22,23,24. This degradation mode could be a significant issue in metal–oxide–semiconductor field-effect transistors because, in such devices, a power circuit turns on the body p–n diode to allow a reflux current to flow during the switching operation. In a previous study, we found the degradation induced by a forward current occurred locally and might originate from threading dislocations24, although the specific defects in the current leakage path were not determined. Identifying these defects is very important for the further improvement of GaN bulk substrates because, while the elimination of all defects would be extremely difficult, the reduction of one type of defect may be feasible.

In the present work, we performed cross-sectional transmission electron microscopy (TEM) analyses of threading dislocations extracted from current leakage paths induced by forward current stress. We also identified the Burgers vector of the dislocations most frequently found at the leakage paths, using the large-angle convergent-beam electron diffraction (LACBED) method25,26.

## Methods

The layered structures of the experimental p–n junctions were grown using metalorganic vapor phase epitaxy in conjunction with commercially available freestanding GaN(0001) substrates prepared via hydride vapor phase epitaxy. The typical threading dislocation density in these specimens was 3 × 105 cm−2 based on the etch pit density using the fused alkali. As shown in Fig. 1, the layered structure was composed of (from top to bottom) a 0.1 μm-thick p+-type GaN contact layer doped with magnesium (Mg) at a concentration of 5 × 1019 cm−3, a 1.5 μm-thick p-type GaN layer doped with Mg at a concentration of 7.7 × 1017 cm−3, a 1.5 μm-thick n-type GaN layer doped with silicon (Si) at a concentration of 3.1 × 1017 cm−3 and an n+-type GaN buffer layer with a Si concentration of 1.8 × 1018 cm−3. The surface electric field was reduced by forming a bevel mesa through the p-type layer at an angle of 6.2° to 7.2° by inductively coupled plasma reactive ion etching12,27. A nickel/gold (Ni/Au) metal stack was deposited as an anode electrode and was subsequently sintered at 500 °C under oxygen to form the Ohmic contact. Finally, a titanium/aluminum/Ni (Ti/Al/Ni) cathode electrode was formed on the reverse side of the substrate. In the present study, we focus on the characterization of three representative diodes with different diameters. Specifically, the anode and junction diameters (Φanode and Φpn) were 60 and 184 μm for diode #1AX, 220 and 342 μm for #1CX, and 320 and 442 μm for #1DX.

The electrical properties of the specimens were sequentially characterized. Reverse bias sweeps up to the breakdown voltage were conducted at 25, 100 and 175 °C, followed by 1 h hold tests at 80% of the breakdown voltage at these respective temperatures. Hold tests performed for a duration of 1 h at a constant current of 1 mA, which corresponded to the avalanche condition, were subsequently carried out at the same temperatures. Following this, continuous forward current stress was applied by increasing the current density in a stepwise manner. The current density, J, during these stress trials was 50, 100, 200 and 500 A/cm2 (normalized by the anode area) and was each applied for 1 h. Those diodes that had exhibited increased reverse leakage current during the forward current tests were observed by emission microscopy (EMS) using an InGaAs detector sensitive over the wavelength range of 900 to 1600 nm. Defect-related carrier recombination sites associated with local leakage paths appeared as luminous points in the resulting EMS images28. It should be noted that these EMS observations were performed from the backside of the device after removing the cathode electrode by polishing. TEM specimens having ($$1\overline{1}00$$) cross-sections were fabricated near the luminous points and 0002 and $$11\overline{2}0$$ two-beam diffractions were assessed. The LACBED analyses were performed using a JEOL JEM-ARM300F at an acceleration voltage of 300 kV. This technique allowed the determination of the Burger vectors associated with dislocations based on analyzing the interactions between high-order Laue zone lines and a threading dislocation line25,26.

## Results and discussion

Figure 2 presents the current density–voltage (JV) curves acquired in conjunction with reverse biases at 25, 100 and 175 °C for three representative diodes. Note that these J data have been normalized by the junction areas. The breakdown voltages at 25 °C were in the range of 191–192 V, and so were close to the ideal avalanche breakdown voltage of 174 V expected from the doping concentration in these devices29,30. The breakdown voltages were found to increase with increasing temperature, which is characteristic of avalanche breakdown12,27. All diodes exhibited repeatable breakdown characteristics, indicating good avalanche capabilities owing to the shallow beveled mesa termination12,27. The leakage currents and avalanche voltages for all diodes were stable throughout each 1 h hold test both at 80% of the breakdown voltage and under avalanche conditions at 25, 100 and 175 °C (see Supplementary Information). These results were in keeping with those of a previous study24 using p–n diodes fabricated on freestanding GaN substrates having threading dislocation densities less than 104 cm−2. It is therefore evident that threading dislocations had a minimal effect on the robustness of such devices when subjected to reverse bias stress.

Figure 3 shows the forward and reverse bias characteristics of the specimens during continuous forward current trials. Diode #1AX, which had the smallest anode diameter (Φanode = 60 μm), showed constant forward and reverse bias properties during the test period. We also confirmed that the other two diodes (with Φanode = 60 and 120 μm) were similarly stable (data not shown). In contrast, the leakage current levels observed in the case of diodes #1CX and #1DX (with respective Φanode values of 220 and 320 μm) rapidly increased with increasing J stress. Similar degradation was demonstrated by the other three diodes with Φanode values of more than 220 μm (data not shown). Figure 4a and b provide EMS images for diodes #1CX and #1DX acquired after continuous J stress tests at reverse biases of − 120 and − 78 V, respectively. Since the EMS observations were performed from the backside of each device, these images have been flipped horizontally so as to present the views from the anode side. Two luminous points, A and B, are apparent in the image of diode #1CX, while three EMS points, C, D and E, can be seen in that of diode #1DX. Based on the average threading dislocation density of 3 × 105 cm−2, 110 and 240 threading dislocations would be expected to be present under the anode electrodes in samples #1CX and #1DX, whereas only two and three luminous points are apparent in the EMS images, respectively. In addition, the diodes with Φanode = 60 and 120 μm that showed no degradation would be expected to contain 8.5 and 34 threading dislocations under the anode electrodes, respectively. These results suggest that only a few threading dislocations provided reverse current leakage paths during the continuous J tests, while the reverse leakage current at the majority remained at the low level as before experiencing the forward current stress.

Figure 5 shows dark-field cross-sectional TEM images acquired at luminous points A and C. The g = 0002 and g = $$11\overline{2}0$$ diffraction conditions allowed the visualization of threading dislocations having screw and edge components, respectively. In the case of luminous point A, one threading dislocation visible only for the 0002 diffraction condition was detected and was assigned to a closed-core threading screw dislocation (TSD). For luminous point C, one closed-core TSD along with a threading edge dislocation (TED) was observed. Both threading dislocations at point C passed through the p–n junction, although they disappeared near the junction as a consequence of the thinning process applied to the TEM specimen. A TSD passing through the junction was found at each of EMS points B, D and E in the degraded diodes #1CX and #1DX, as summarized in Table 1. We also performed a TEM analysis for the EMS point previously examined24 in degraded p-n diodes on an acidic ammonothermal-grown freestanding GaN substrate having a threading dislocation density of less than 104 cm−2 and found a TSD (data not shown). As summarized in Table 1, we detected the common TSDs at eleven EMS points for p–n diodes on two different types of GaN substrates. These results suggest that closed-core TSDs provided leakage pathways after the application of forward current stress. In the p–n diodes of the present study, the portion of TSDs to the total threading dislocations is unknown because it is not easy to separate TSDs from the threading mixed dislocations (TMDs) even using the etch pit methods31. In general, the ratio of the number of TSDs to the total number of threading dislocations in freestanding GaN substrates will be relatively small31,32,33. This may explain the robust nature of some p-n diodes incorporating threading dislocations and the small number of luminous points compared with the total number of threading dislocations seen in the EMS images after continuous J stress.

LACBED analyses were performed to identify the Burgers vectors, and Fig. 6a and b show the two-beam bright-field TEM images obtained from luminous point D, which indicate the existence of one TSD. The Burgers vector for this TSD can be expressed as b = [000x], and Fig. 6c and d present LACBED images for this dislocation. It should be noted that for higher order diffractions g can interact with a threading dislocation line, to split into multiple lines whose number is $$n = {\varvec{g}}\cdot {\varvec{b}}$$ 25,26. Figure 6d shows the magnified LACBED pattern near g = 0008 and exhibits eight split lines (n = 8). We were therefore able to determine the Burgers vector for the TSD associated with point D as b = [0001]. The same analysis was performed for the TSD at emission point A and for the TSD at emission points Y and Z in the previously examined diode on the acidic ammonothermal-grown GaN substrate having the threading dislocation density less than 104 cm−2, and the identical conclusions of b = [0001] were obtained. These results suggest that simple TSDs having b = 1c provided leakage paths after the continuous J stress tests although we cannot say all TSDs with b = 1c being the leakage pathways due to the small number of LACBED examinations at the present. In previous work using p–n diodes with much lower threading dislocation densities, there was good agreement between EMS points acting as leakage paths and the threading dislocations in the topographic images before the stress test24. This indicates TSDs were not mobile during the J stress test. Furthermore, other types of threading dislocations were not observed near the leakage spots in Ref.24. Therefore, we propose that interactions between threading dislocations involving motion during the J stress tests were unlikely. Nakano et al.34 theoretically suggested that complexes formed from Mg atoms and TSDs can act as current leakage paths in p-type GaN. In the case that current injection promotes Mg diffusion along TSDs, Nakano’s suggestion could explain the present degradation mode, although further work is required to identify the conduction mechanism at the TSDs.

## Conclusions

Threading dislocations thought to act as current leakage paths after continuous forward current tests in GaN p–n junctions were extracted and characterized. Trials with p–n diodes fabricated on freestanding GaN substrates with threading dislocation densities of approximately 3 × 105 cm−2 showed that the leakage current was increased for devices with Φanode values of more than 220 μm during forward current injection, whereas diodes having a Φanode of 60 μm were generally stable. EMS observations from the backside of each device identified the current leakage paths and the same closed-core TSDs were identified near each luminous point in these images. The Burgers vector of the extracted TSDs was identified as b = [0001]. The results of this work suggest that simple TSDs at least with b = 1c provided significant leakage pathways in response to excitation during the continuous forward current stress trials.

## Data availability

The data that support the findings of this study are available from the corresponding author upon reasonable request.

## References

1. Nie, H., Diduck, Q., Alvarez, B., Edwards, A. P., Kayes, B. M., Zhang, M., Ye, G., Prunty, T., Bour, D. & Kizilyalli, I. C. 1.5-kV and 2.2-mΩ-cm2 Vertical GaN Transistors on Bulk-GaN Substrates. IEEE Electron Device Lett. 35, 939 (2014).

2. Oka, T., Ina, T., Ueno, Y. & Nishii. J. 1.8 mΩ·cm2 vertical GaN-based trench metal–oxide–semiconductor field-effect transistors on a free-standing GaN substrate for 1.2-kV-class operation. Appl. Phys. Exp. 8, 054101 (2015).

3. Shibata, D., Kajitani, R., Ogawa, M., Tanaka, K., Tamura, S., Hatsuda, T., Ishida, M. & Ueda, T. 1.7 kV / 1.0 mΩcm2 normally-off vertical GaN transistor on GaN substrate with regrown p-GaN/AlGaN/GaN semipolar gate structure. In IEEE International Electron Devices Meeting (IEEE, San Francisco, 2016), p. 248.

4. Zhang, Y., Sun, M., Piedra, D., Hu, J., Liu, Z., Lin, Y., Gao, X., Shepard, K. & Palacios T. 1200 V GaN vertical fin power field-effect transistors. In IEEE International Electron Devices Meeting (IEEE, San Francisco, 2017), p. 215.

5. Oka, T. Recent development of vertical GaN power devices. Jpn. J. Appl. Phys. 58, SB0805 (2019).

6. Tanaka, R., Takashima, S., Ueno, K., Matsuyama, H. & Edo, M. Demonstration of 1200 V/1.4 mΩcm2 vertical GaN planar MOSFET fabricated by an all ion implantation process. Jpn. J. Appl. Phys., 59, SGGD02 (2020).

7. Liu, J., Xiao, M., Zhang, Y., Pidaparthi, S., Cui, H., Edwards, A., Baubutr, L., Meier, W., Coles, C. & Drowley, C. 1.2 kV vertical GaN Fin JFETs with robust avalanche and fast switching capabilities. In IEEE International Electron Devices Meeting (IEEE, Virtual, 2020), p. 477.

8. Liu, J., Xiao, M., Zhang, R., Pidaparthi, S., Cui, H., Edwards, A., Craven, M., Baubutr, L., Drowley, C. & Zhang., Y. 1.2-kV vertical GaN Fin-JFETs: high-temperature characteristics and avalanche capability. IEEE Trans. Electron. Devices 68, 2025 (2021).

9. Kachi, T. Recent progress of GaN power devices for automotive applications. Jpn. J. Appl. Phys. 53, 100210 (2014).

10. Kachi, T. GaN devices for automotive application and their challenges in adoption. In IEEE International Electron Devices Meeting (IEEE, San Francisco, 2018), p. 452.

11. Kizilyalli, I. C., Edwards, A. P., Nie, H., Disney, D. & Bour, D. High voltage vertical GaN p-n diodes with avalanche capability. IEEE Trans. Electron Devices 60, 3067 (2013).

12. Maeda, T. et al. Design and fabrication of GaN p-n junction diodes with negative Beveled-Mesa termination. IEEE Electron Device Lett. 40, 941 (2019).

13. Fukushima, H., Usami, S., Ogura, M., Ando, Y., Tanaka, A., Deki, M., Kushimoto, M., Nitta, S., Honda, Y. & Amano, H. Vertical GaN p–n diode with deeply etched mesa and the capability of avalanche breakdown. Appl. Phys. Exp. 12, 026502 (2019).

14. Ji, D., Li, S., Ercan, B., Ren, C. & Chowdhury, S. Design and fabrication of ion-implanted moat etch termination resulting in 0.7 mΩ·cm2/1500 V GaN diodes. IEEE Electron Device Lett. 41, 264 (2020).

15. Ohta, H. et al. Two-step mesa structure GaN p-n diodes with low on-resistance, high breakdown voltage, and excellent avalanche capabilities. IEEE Electron Device Lett. 41, 123 (2020).

16. Matys, M., Ishida, T., Nam, K. P., Sakurai, H., Kataoka, K., Narita, T., Uesugi, T., Bockowski, M., Nishimura, T., Suda, J. & Kachi, T. Design and demonstration of nearly-ideal edge termination for GaN p–n junction using Mg-implanted field limiting rings. Appl. Phys. Exp. 14, 074002 (2021).

17. Kachi, T. & Uesugi, T. Evaluation of GaN substrate for vertical GaN power device applications. Sensors Mater. 25, 219 (2013).

18. Usami, S., Ando, Y., Tanaka, A., Kentaro Nagamatsu, K., Deki, M., Kushimoto, M., Nitta, S., Honda, Y., Amano, H., Sugawara, Y., Yong-Zhao Yao, Y.-Z. & Ishikawa, Y. Correlation between dislocations and leakage current of p-n diodes on a freestanding GaN substrate. Appl. Phys. Lett. 112, 182106 (2018).

19. Usami, S., Tanaka, A., Fukushima, H., Ando, Y., Deki, M., Nitta, S., Honda, Y., & Amano, H. Correlation between nanopipes formed from screw dislocations during homoepitaxial growth by metal-organic vapor-phase epitaxy and reverse leakage current in vertical p–n diodes on a free-standing GaN substrates. Jpn. J. Appl. Phys. 58, SCCB24 (2019).

20. Usami, S., Mayama, N., Toda, K., Tanaka, A., Deki, M., Nitta, S., Honda, Y., & Amano, H. Direct evidence of Mg diffusion through threading mixed dislocations in GaN p–n diodes and its effect on reverse leakage current. Appl. Phys. Lett. 114, 232105 (2019).

21. Kanechika, M., Yamaguchi, S., Imanishi, M. & Mori, Y. Evaluation of dislocations under the electrodes of GaN pn diodes by X-ray topography. Jpn. J. Appl. Phys. 58, SCCD22 (2019).

22. Kizilyalli, I. C., Bui-Quanga, P., Disney, D., Bhatia, H. & Aktas, O. Reliability studies of vertical GaN devices based on bulk GaN substrates. Microelectron. Reliab. 55, 1654 (2015).

23. Fabris, E. et al. Degradation of GaN-on-GaN vertical diodes submitted to high current stress. Microelectron. Reliab. 88–90, 568 (2018).

24. Narita, T. Nagasato, Y., Kanechika, M., Kondo T., Uesugi, T., Tomita, K., Ikeda, S., Yamaguchi, S., Kimoto, Y., Kosaki, M., Oka T., Kojima, J. & Suda, J. Increase of reverse leakage current at homoepitaxial GaN p-n junctions induced by continuous forward current stress. Appl. Phys. Lett. 118, 253501 (2021).

25. Chernsa, D. & Morniroli, J.-P. Analysis of partial and stair-rod dislocations by large angle convergent beam electron diffraction. Ultramicroscopy 53, 167 (1994).

26. Kokubo, N., Tsunooka, Y., Fujie, F., Ohara, J., Onda, S., Yamada, H., Shimizu, M., Harada, S., Tagawa, M. & Ujihara, T. Determination of edge-component Burgers vector of threading dislocations in GaN crystal by using Raman mapping. Appl. Phys. Exp. 11, 111001 (2018).

27. Maeda, T., Narita, T., Ueda, H., Kanechika, M., Uesugi, T., Kachi, T., Kimoto, T., Horita, M. & Suda, J. Parallel-plane breakdown fields of 2.8–3.5 MV/cm in GaN-on-GaN p-n junction diodes with double-side-depleted shallow bevel termination. In IEEE International Electron Devices Meeting (IEEE, San Francisco, 2018), p. 687.

28. Meneghini, M., Trivellin, N., Pavesi, M., Manfredi, M., Zehnder, U., Hahn, B., Meneghesso, G. & Zanoni, E. Leakage current and reverse-bias luminescence in InGaN-based light emitting diodes. Appl. Phys. Lett. 95, 173507 (2009).

29. Maeda, T., Narita, T., Yamada, S., Kachi, T., Kimoto, T., Horita, M. & Suda, J. Impact ionization coefficients in GaN measured by above- and sub-Eg illuminations for p/n+ junction. In IEEE International Electron Devices Meeting (IEEE, San Francisco, 2019), p. 70.

30. Maeda, T., Narita, T., Yamada, S., Kachi, T., Kimoto, T., Horita, M. & Suda, J. Impact ionization coefficients and critical electric field in GaN. J. Appl. Phys. 129, 185702 (2021).

31. M. Albrecht, M., Weyher, J. L., Lucznik, B., Grzegory, I., and Porowski, S. Nonradiative recombination at threading dislocations in n-type GaN: Studied by cathodoluminescence and defect selective etching, Appl. Phys. Lett. 92, 231909 (2008).

32. Sintonen, S., Suihkonen, S., Jussila, H., Danilewsky, A., Stankiewicz, R., Tuomi, T. O, and Lipsanen, H. Large-area analysis of dislocations in ammonothermal GaN by synchrotron radiation X-ray topography. Appl. Phys. Exp. 7, 091003 (2014).

33. Yao, Y. et al. Correlation between structural properties and nonradiative recombination behaviors of threading dislocations in freestanding GaN substrates grown by hydride vapor phase epitaxy. CrystEngComm 48, 8277 (2020).

34. Nakano, T., Harashima, Y., Chokawa, K., Shiraishi, K., Oshiyama, A., Kangawa, Y., Usami, S., Mayama, N., Toda, K., Tanaka, A., Honda, Y. & Amano, H. Screw dislocation that converts p-type GaN to n-type: Microscopic study on Mg condensation and leakage current in p–n diodes. Appl. Phys. Lett. 117, 012105 (2020).

## Acknowledgements

The authors thank the Center for Integrated Research of Future Electronics, Transformative Electronics Facilities (C-TEFs) at Nagoya University for fabricating the devices used in this work. The synchrotron radiation X-ray topography analyses were performed at the BL16B2 (Proposal Nos. 2018B5370, 2019A5370, 2019B5370 and 2020A5370) and BL20B2 (Proposal Nos. 2019B1042 and 2020A1039) beamlines at the SPring-8 facility with the approval of the Japan Synchrotron Radiation Research Institute (JASRI).

## Author information

Authors

### Contributions

T. Narita planned the series of experiments and wrote the manuscript. M. Kanechika evaluated the electrical properties of the samples. J. Kojima and H. Watanabe performed the TEM and LACBED analyses. T. Kondo and T. Uesugi fabricated p-n diodes with a beveled mesa structure. S. Yamaguchi and Y. Kimoto contributed to the synchrotron X-ray topography experiments along with M. Kanechika. Although the X-ray topographic image did not appear in this paper, the results were utilized to select the test diodes. K. Tomita performed the MOVPE growth of the experimental samples along with T. Narita. Y. Nagasato and S. Ikeda designed the test element group pattern for the diodes and performed the initial characterizations of the diodes. M. Kosaki and T. Oka contributed to the identification of defects using emission microscopy. J. Suda led the research team. All authors discussed the contents of the manuscript.

### Corresponding author

Correspondence to Tetsuo Narita.

## Ethics declarations

### Competing interests

The authors declare no competing interests.

### Publisher's note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Rights and permissions

Reprints and Permissions

Narita, T., Kanechika, M., Kojima, J. et al. Identification of type of threading dislocation causing reverse leakage in GaN p–n junctions after continuous forward current stress. Sci Rep 12, 1458 (2022). https://doi.org/10.1038/s41598-022-05416-3

• Accepted:

• Published:

• DOI: https://doi.org/10.1038/s41598-022-05416-3


text:
# Collect powers of variables and integers separately?

Let expr contain a sum of powers of x with some coefficients ci. The exponents of x can contain variables and/or integers. I would like to define a function MyCollect in Mathematica which would first collect all powers containing variables and would then collect all powers containing integers within the first collection. For example, such that if:

expr = c0 x^(a+b)+c1 x^(a+b+1)+c2 x^(a+b+2)+c3 x^(a+b+2)+c4 x^(a+b+2)+c5 x^(a)+c6 x^(a+1)+c7 x^(a+1)

the result would be:

MyCollect[expr]

x^(a)(c5 + x(c6+c7)) + x^(a+b)(c0 + x c1 + x^2(c2 + c3 + c4))

Is there a convenient way to do this? Thanks for any suggestion!

EDIT

Here is a second, more complicated example

expr = c0 x^(a+b)+c1 x^(a+b+1)+c2 x^(a+b+2)+c3 x^(2a+b+2)+c4 x^(a+b+2)+c5 x^(a)+c6 x^(a+1)+c7 x^(a+1)+c8 x^(a+c+1)+c9 x^(a+c)

Desired output of MyCollect[expr]:

x^(a)(c5 +x(c6+c7)) + x^(a+b)(c0 +x c1+x^2(c2+c4)) + x^(2a+b)(x^2 c3) + x^(a+c)(c9+x c8)

All unique combinations of powers involving variables are collected first, and then the remaining integer powers are collected at a second level, so to say.

Update: This matches the evaluated form of your desired output for each example:

fn = Collect[#, x^y_ /; FreeQ[y, _Integer], Apart] &;

Test:

expr1 = c0 x^(a + b) + c1 x^(a + b + 1) + c2 x^(a + b + 2) + c3 x^(a + b + 2) +
c4 x^(a + b + 2) + c5 x^(a) + c6 x^(a + 1) + c7 x^(a + 1);

target1 = x^(a) (c5 + x (c6 + c7)) + x^(a + b) (c0 + x c1 + x^2 (c2 + c3 + c4));

expr2 = c0 x^(a + b) + c1 x^(a + b + 1) + c2 x^(a + b + 2) + c3 x^(2 a + b + 2) +
c4 x^(a + b + 2) + c5 x^(a) + c6 x^(a + 1) + c7 x^(a + 1) + c8 x^(a + c + 1) +
c9 x^(a + c);

target2 = x^(a) (c5 + x (c6 + c7)) + x^(a + b) (c0 + x c1 + x^2 (c2 + c4)) +
x^(2 a + b) (x^2 c3) + x^(a + c) (c9 + x c8);

fn[expr1]

fn[expr2]

fn[expr1] === target1

fn[expr2] === target2

x^a (c5 + (c6 + c7) x) + x^(a + b) (c0 + c1 x + (c2 + c3 + c4) x^2)

c3 x^(2 + 2 a + b) + x^a (c5 + (c6 + c7) x) + x^(a + c) (c9 + c8 x) +
x^(a + b) (c0 + c1 x + (c2 + c4) x^2)

True

True

• Yes, it seems to do the right thing at least for the short example above. I'll have to test if it will still work accordingly in more complicated cases. But I see no reason why it should not. – Kagaratsch Oct 28 '14 at 0:25
• I just wonder what the syntax /@ means? – Kagaratsch Oct 28 '14 at 0:26
• Now I tried a slightly more complicated example and unfortunately the result was not correct. See my edit above. – Kagaratsch Oct 28 '14 at 0:33
• @Kagaratsch Please include the desired output for the second example. – Mr.Wizard Oct 28 '14 at 0:41
• /@ is a short for map[],you can search it in the "Help" document of Mathematic – user21730 Oct 28 '14 at 1:17

format: plain


text:
It is currently 23 Sep 2017, 06:16

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# A term an is called a “cusp” of a sequence if an is an integer but an+

Author Message
TAGS:

### Hide Tags

Math Expert
Joined: 02 Sep 2009
Posts: 41695

Kudos [?]: 124575 [1], given: 12079

A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

23 Jan 2015, 07:25
1
KUDOS
Expert's post
14
This post was
BOOKMARKED
00:00

Difficulty:

95% (hard)

Question Stats:

51% (01:58) correct 49% (01:58) wrong based on 191 sessions

### HideShow timer Statistics

A term an is called a “cusp” of a sequence if $$a_n$$ is an integer but $$a_{n+1}$$ is not an integer. If $$a_5$$ is a cusp of the sequence a1,a2,…,an,… in which $$a_1=k$$ and $$a_n=-2\frac{(a_{n-1})}{3}$$ for all n>1, then k could be equal to:

A. 3
B. 16
C. 108
D. 162
E. 243

Kudos for a correct solution.
[Reveal] Spoiler: OA

_________________

Kudos [?]: 124575 [1], given: 12079

Math Forum Moderator
Joined: 02 Aug 2009
Posts: 4912

Kudos [?]: 5245 [0], given: 112

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

23 Jan 2015, 08:13
Expert's post
1
This post was
BOOKMARKED
ans E 243....a5 is int and a6 is not int so a5 should be div by 3 and a6 not therefore 3^5...
_________________

Absolute modulus :http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html

Kudos [?]: 5245 [0], given: 112

Manager
Joined: 13 Dec 2013
Posts: 59

Kudos [?]: 25 [0], given: 34

Location: Iran (Islamic Republic of)
Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Jan 2015, 00:46
THE CORRECT ANSWER IS B NOT E....

WE are told that in a sequence we have first term a1 equal to k and we are given a formula to obtain each of the progression based on that formula

we are given an=-2 (an-1)/3 for n>1 based on a1 is k so we should have a2= -2*k/3

TO obtain a3 , we should replace a2 in the formula and we get a3= -2 *(-2*k/3) /3 so we can get a3=4*k/9

in the same way we can obtain a4 , a4 = -2 * (4k/9)/3 = -8k/27 and for a5 we replace a4 in the formula and get : -2* (-8k/27)/3 = 16k/81

so a5 is : 16k/81 in this point we can see that k is an integer that MUST divisible by 16 and in the given options ONLY OPTION B is the OPTION which is DIVISIBLE BY 16

SO ,the correct ans IS B

Kudos [?]: 25 [0], given: 34

Senior Manager
Joined: 27 Oct 2013
Posts: 254

Kudos [?]: 125 [0], given: 79

Location: India
Concentration: General Management, Technology
GMAT Date: 03-02-2015
GPA: 3.88
Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Jan 2015, 01:54
1
This post was
BOOKMARKED
Here we go----

a1 = K

So to be a "cusp" of a sequence

a2 must not be an integer....

So, a2 = -2/3 * ( a1 )

a2 = -2/3 * ( K )

Substitute values for K from the options

A. 3 (integer)
B. 16 (not an integer)
C. 108 (integer)
D. 162 (integer)
E. 243 (integer)

Option B is correct

Kudos [?]: 125 [0], given: 79

Math Forum Moderator
Joined: 02 Aug 2009
Posts: 4912

Kudos [?]: 5245 [0], given: 112

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Jan 2015, 03:54
THE CORRECT ANSWER IS B NOT E....

WE are told that in a sequence we have first term a1 equal to k and we are given a formula to obtain each of the progression based on that formula

we are given an=-2 (an-1)/3 for n>1 based on a1 is k so we should have a2= -2*k/3

TO obtain a3 , we should replace a2 in the formula and we get a3= -2 *(-2*k/3) /3 so we can get a3=4*k/9

in the same way we can obtain a4 , a4 = -2 * (4k/9)/3 = -8k/27 and for a5 we replace a4 in the formula and get : -2* (-8k/27)/3 = 16k/81

so a5 is : 16k/81 in this point we can see that k is an integer that MUST divisible by 16 and in the given options ONLY OPTION B is the OPTION which is DIVISIBLE BY 16

SO ,the correct ans IS B

how can 16k/81 be an integer if k is div by 16.. a5 will be an int if it is div by 81
_________________

Absolute modulus :http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html

Kudos [?]: 5245 [0], given: 112

Manager
Joined: 13 Dec 2013
Posts: 59

Kudos [?]: 25 [0], given: 34

Location: Iran (Islamic Republic of)
Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Jan 2015, 04:41
Dear Chatan 2 U,

As the problem says a1 is integer so a2 is not so a3 is integer and so on .therefore a5 is integer too.

if we consider X as integer, and placed it infornt of a5 we reach to this equation:

X= 16k/81 and in this case for finding k we change the equation to K= 81*X/16 in this state we must obtain K as integer and as 81 is not divisible by 16 so in order to K to be integer so X must be multiple of 16 and we see here ONLY option B is MULTIPLE of 16 ,SO ans is B

Kudos [?]: 25 [0], given: 34

Math Forum Moderator
Joined: 02 Aug 2009
Posts: 4912

Kudos [?]: 5245 [0], given: 112

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Jan 2015, 05:45
Dear Chatan 2 U,

As the problem says a1 is integer so a2 is not so a3 is integer and so on .therefore a5 is integer too.

if we consider X as integer, and placed it infornt of a5 we reach to this equation:

X= 16k/81 and in this case for finding k we change the equation to K= 81*X/16 in this state we must obtain K as integer and as 81 is not divisible by 16 so in order to K to be integer so X must be multiple of 16 and we see here ONLY option B is MULTIPLE of 16 ,SO ans is B

hi,
i again feel what he means is that at a(n), the value changes from integer to non integer..
second point, a5 has to be integer so k being integer does not solve the purpose .
a5=16*k/81
if a1=k = 16 then a5=16*16/81, which is not integer
_________________

Absolute modulus :http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html

Kudos [?]: 5245 [0], given: 112

Math Expert
Joined: 02 Sep 2009
Posts: 41695

Kudos [?]: 124575 [0], given: 12079

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

26 Jan 2015, 04:21
Expert's post
4
This post was
BOOKMARKED
Bunuel wrote:
A term an is called a “cusp” of a sequence if $$a_n$$ is an integer but $$a_{n+1}$$ is not an integer. If $$a_5$$ is a cusp of the sequence a1,a2,…,an,… in which $$a_1=k$$ and $$a_n=-2\frac{(a_n-1)}{3}$$ for all n>1, then k could be equal to:

A. 3
B. 16
C. 108
D. 162
E. 243

Kudos for a correct solution.

VERITAS PREP OFFICIAL SOLUTION:

As with many sequence problems, the wording of this question is designed to be horribly abstract. Let’s just focus on the fact that a5 is an integer but a6 is not an integer.

Putting the sequence into words can help. What do we do to find the next value? We take the previous value and multiply by −2/3. Or even more colloquially, we:

First, flip the sign of the previous one. Second, multiply it by two. Third, divide it by three.

So the second term will be −2/3 times the first one. The third term will be −2/3 times the second one. And so on.

Now, keep in mind that our goal is to find a value of k that will be an integer by the fifth term but not an integer by the sixth term. And this can make your job a lot easier. Positive vs. negative won’t have any bearing on whether a term is an integer or not, and the major operation that will control that will be division. Consider k = 6 as an example (since there are 2s and 3s all over this problem let’s pick a number that’s divisible by both). The first term would be 6, then the second term would be −2/3(6) or -4. Then the third term won’t be an integer, as the “divide by 3” part of the operation will leave you with a decimal.

So when you see that the 5th term of the sequence is going to be:

(−2/3)(−2/3)(−2/3)(−2/3)k, and will be an integer, but that the 6th term of the sequence will be:

(−2/3)(−2/3)(−2/3)(−2/3)(−2/3)k, and will not be an integer, you should see that the real question is “how many times can we evenly divide k by 3?”.

The answer, then, is 4, as it’s that fifth iteration of −2/3 that takes us from “integer” to “noninteger” status.

So kmust contain exactly four 3s, since 81=3^4 and since a5 contains no 3s (recall that a5 was an integer but not a multiple of 3).

Now, factor the answer choices. 3 is already prime factored, but it’s far short of four 3s, so it’s incorrect. 16=2^4; this has no 3s at all, so it’s also incorrect. 108=2^2*3^3; this answer is closer, but it’s still one 3 short, so it’s incorrect too. 162=(2)3^4; that’s the four 3s we need, so this is the correct answer. Finally, 243=3^5; that’s one 3 too many – we needed exactly four – so this is also incorrect.

_________________

Kudos [?]: 124575 [0], given: 12079

Math Forum Moderator
Joined: 02 Aug 2009
Posts: 4912

Kudos [?]: 5245 [0], given: 112

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

26 Jan 2015, 04:26
thanks bunuel..
i was looking for 81 in ans and then settled for next power of 3 ie 243..
how could i miss out 162, a multiple of 81..
_________________

Absolute modulus :http://gmatclub.com/forum/absolute-modulus-a-better-understanding-210849.html#p1622372
Combination of similar and dissimilar things : http://gmatclub.com/forum/topic215915.html

Kudos [?]: 5245 [0], given: 112

Intern
Joined: 03 Aug 2014
Posts: 20

Kudos [?]: [0], given: 18

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

29 Apr 2015, 19:36
is the portion in brackets An - 1 or A(n-1)? It looks like the former.

Kudos [?]: [0], given: 18

Intern
Joined: 26 Apr 2015
Posts: 4

Kudos [?]: 1 [0], given: 4

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

29 Apr 2015, 19:49
Bunnel Great explanation

Kudos [?]: 1 [0], given: 4

GMAT Club Legend
Joined: 09 Sep 2013
Posts: 17615

Kudos [?]: 271 [0], given: 0

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 May 2016, 20:08
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________

Kudos [?]: 271 [0], given: 0

GMAT Club Legend
Joined: 09 Sep 2013
Posts: 17615

Kudos [?]: 271 [0], given: 0

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

11 Jun 2017, 07:02
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________

Kudos [?]: 271 [0], given: 0

Intern
Joined: 29 May 2017
Posts: 11

Kudos [?]: 1 [1], given: 6

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

13 Jun 2017, 08:48
1
KUDOS
hi. the original post shows $$a_n=a_n - 1$$. but in reality it is $$a_{n-1}$$. not sure if my point is coming across as i am new to writing fractions etc on the forum

Kudos [?]: 1 [1], given: 6

Math Expert
Joined: 02 Sep 2009
Posts: 41695

Kudos [?]: 124575 [0], given: 12079

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

13 Jun 2017, 09:02
Mansoor50 wrote:
hi. the original post shows $$a_n=a_n - 1$$. but in reality it is $$a_{n-1}$$. not sure if my point is coming across as i am new to writing fractions etc on the forum

You are right. Edited the question. Thank you.
_________________

Kudos [?]: 124575 [0], given: 12079

Intern
Joined: 17 Jul 2017
Posts: 17

Kudos [?]: 1 [1], given: 4

A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

03 Aug 2017, 11:35
1
KUDOS
I think if you get this right you're on the cusp of greatness. The question isn't too difficult once you understand what they are asking.

So we know
A1=K
A2 therefore =-2k/3 Because A2=-2(k)/3
A3= 4k/9 because A3 = -2(a2)/3 = -2 ((2k/3)/3) which equals 4k/9
A4 = -8k/27
A5 = 16K/81
A6 = -32K/243

So now we need to look at the solutions. Breaking the numbers into prime factorization is the trick for this part.

1) 3 well we can see that A5 =(16*3)/81 is not an integer
2) 16 is wrong as A5 = (2^4) * (2^4) / (3^4). Well (2^8) /(3^3) is clearly not an integer
3) 108 is wrong as A5 = [(2^4)* (9X13)] / 9^2 . Again we only have one power of 9 on the top and 2 on the bottom. Clearly not an integer
4) 162 = (9^2)* (2^4) / 9^2 this will be an integer

and A6 = -[2^5 * (9^2) *2)] / (9^2 X 3). Notice we have an extra 3 on the bottom therefore this isn't an integer.

5) We can solve E for fun
A5= [(2^5) * (9^2)*3] / [(9^2] Clearly an integer
A6= 243=(9^2) X 3 . so [(2^5) X (9^2 )*3] / [(9^2) X 3] Clearly an integer

Last edited by Samuelboyle96 on 24 Aug 2017, 10:41, edited 1 time in total.

Kudos [?]: 1 [1], given: 4

Intern
Joined: 08 Mar 2016
Posts: 39

Kudos [?]: 5 [0], given: 13

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

04 Aug 2017, 03:51
Bunuel wrote:
Bunuel wrote:
A term an is called a “cusp” of a sequence if $$a_n$$ is an integer but $$a_{n+1}$$ is not an integer. If $$a_5$$ is a cusp of the sequence a1,a2,…,an,… in which $$a_1=k$$ and $$a_n=-2\frac{(a_n-1)}{3}$$ for all n>1, then k could be equal to:

A. 3
B. 16
C. 108
D. 162
E. 243

Kudos for a correct solution.

VERITAS PREP OFFICIAL SOLUTION:

As with many sequence problems, the wording of this question is designed to be horribly abstract. Let’s just focus on the fact that a5 is an integer but a6 is not an integer.

Putting the sequence into words can help. What do we do to find the next value? We take the previous value and multiply by −2/3. Or even more colloquially, we:

First, flip the sign of the previous one. Second, multiply it by two. Third, divide it by three.

So the second term will be −2/3 times the first one. The third term will be −2/3 times the second one. And so on.

Now, keep in mind that our goal is to find a value of k that will be an integer by the fifth term but not an integer by the sixth term. And this can make your job a lot easier. Positive vs. negative won’t have any bearing on whether a term is an integer or not, and the major operation that will control that will be division. Consider k = 6 as an example (since there are 2s and 3s all over this problem let’s pick a number that’s divisible by both). The first term would be 6, then the second term would be −2/3(6) or -4. Then the third term won’t be an integer, as the “divide by 3” part of the operation will leave you with a decimal.

So when you see that the 5th term of the sequence is going to be:

(−2/3)(−2/3)(−2/3)(−2/3)k, and will be an integer, but that the 6th term of the sequence will be:

(−2/3)(−2/3)(−2/3)(−2/3)(−2/3)k, and will not be an integer, you should see that the real question is “how many times can we evenly divide k by 3?”.

The answer, then, is 4, as it’s that fifth iteration of −2/3 that takes us from “integer” to “noninteger” status.

So kmust contain exactly four 3s, since 81=3^4 and since a5 contains no 3s (recall that a5 was an integer but not a multiple of 3).

Now, factor the answer choices. 3 is already prime factored, but it’s far short of four 3s, so it’s incorrect. 16=2^4; this has no 3s at all, so it’s also incorrect. 108=2^2*3^3; this answer is closer, but it’s still one 3 short, so it’s incorrect too. 162=(2)3^4; that’s the four 3s we need, so this is the correct answer. Finally, 243=3^5; that’s one 3 too many – we needed exactly four – so this is also incorrect.

Missed the part when you say "since a5 contains no 3s (recall that a5 was an integer but not a multiple of 3)."

why do we say that a5 contains no 3's ?

Kudos [?]: 5 [0], given: 13

Intern
Joined: 17 Jul 2017
Posts: 17

Kudos [?]: 1 [0], given: 4

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

04 Aug 2017, 06:45
SOUMYAJIT_ wrote:
Bunuel wrote:
Bunuel wrote:
A term an is called a “cusp” of a sequence if $$a_n$$ is an integer but $$a_{n+1}$$ is not an integer. If $$a_5$$ is a cusp of the sequence a1,a2,…,an,… in which $$a_1=k$$ and $$a_n=-2\frac{(a_n-1)}{3}$$ for all n>1, then k could be equal to:

A. 3
B. 16
C. 108
D. 162
E. 243

Kudos for a correct solution.

VERITAS PREP OFFICIAL SOLUTION:

As with many sequence problems, the wording of this question is designed to be horribly abstract. Let’s just focus on the fact that a5 is an integer but a6 is not an integer.

Putting the sequence into words can help. What do we do to find the next value? We take the previous value and multiply by −2/3. Or even more colloquially, we:

First, flip the sign of the previous one. Second, multiply it by two. Third, divide it by three.

So the second term will be −2/3 times the first one. The third term will be −2/3 times the second one. And so on.

Now, keep in mind that our goal is to find a value of k that will be an integer by the fifth term but not an integer by the sixth term. And this can make your job a lot easier. Positive vs. negative won’t have any bearing on whether a term is an integer or not, and the major operation that will control that will be division. Consider k = 6 as an example (since there are 2s and 3s all over this problem let’s pick a number that’s divisible by both). The first term would be 6, then the second term would be −2/3(6) or -4. Then the third term won’t be an integer, as the “divide by 3” part of the operation will leave you with a decimal.

So when you see that the 5th term of the sequence is going to be:

(−2/3)(−2/3)(−2/3)(−2/3)k, and will be an integer, but that the 6th term of the sequence will be:

(−2/3)(−2/3)(−2/3)(−2/3)(−2/3)k, and will not be an integer, you should see that the real question is “how many times can we evenly divide k by 3?”.

The answer, then, is 4, as it’s that fifth iteration of −2/3 that takes us from “integer” to “noninteger” status.

So kmust contain exactly four 3s, since 81=3^4 and since a5 contains no 3s (recall that a5 was an integer but not a multiple of 3).

Now, factor the answer choices. 3 is already prime factored, but it’s far short of four 3s, so it’s incorrect. 16=2^4; this has no 3s at all, so it’s also incorrect. 108=2^2*3^3; this answer is closer, but it’s still one 3 short, so it’s incorrect too. 162=(2)3^4; that’s the four 3s we need, so this is the correct answer. Finally, 243=3^5; that’s one 3 too many – we needed exactly four – so this is also incorrect.

Missed the part when you say "since a5 contains no 3s (recall that a5 was an integer but not a multiple of 3)."

why do we say that a5 contains no 3's ?

My solution above is better than Veritas. Veritas explains solutions as if you're a math genius and just missed the answer because you ran out of time. They don't break down the problem thoroughly for those who make mistakes in a number theory. I did above.

Kudos [?]: 1 [0], given: 4

Intern
Joined: 09 Mar 2017
Posts: 37

Kudos [?]: 2 [0], given: 23

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Aug 2017, 09:21
Samuelboyle96 wrote:
I think if you get this right you're on the cusp of greatness. The question isn't too difficult once you understand what they are asking.

So we know
A1=K
A2 therefore =-2k/3 Because A2=-2(k)/3
A3= 4k/9 because A3 = -2(a2)/3 = -2 ((2k/3)/3) which equals 4k/9
A4 = -8k/27
A5 = 16K/81
A6 = -32K/243

So now we need to look at the solutions. Breaking the numbers into prime factorization is the trick for this part.

1) 3 well we can see that A5 =(16*3)/81 is not an integer
2) 16 is wrong as A5 = (2^4) * (2^4) / (3^4). Well (2^8) /(3^3) is clearly not an integer
3) 108 is wrong as A5 = [(2^4)* (9X13)] / 9^2 . Again we only have one power of 9 on the top and 2 on the bottom. Clearly not an integer
4) 162 = (9^2)* (2^4) / 9^2 this will be an integer

and A6 = -[2^5 * (9^2) *2)] / (9^2 X 3). Notice we have an extra 3 on the bottom therefore this isn't an integer.

5) We can solve E for fun
A5= [(2^5) * (9^2)*3] / [(9^2)X 3] Clearly an integer
A6= 243=(9^2) X 3 . so [(2^5) X (9^2 )*3] / [(9^2) X 3] Clearly an integer

But this answer is wrong for 5), since you're dividing a5 by 9^2 *3, when you should really just be dividing by 9^2.

Kudos [?]: 2 [0], given: 23

Intern
Joined: 17 Jul 2017
Posts: 17

Kudos [?]: 1 [0], given: 4

Re: A term an is called a “cusp” of a sequence if an is an integer but an+ [#permalink]

### Show Tags

24 Aug 2017, 10:40
brandon7 wrote:
Samuelboyle96 wrote:
I think if you get this right you're on the cusp of greatness. The question isn't too difficult once you understand what they are asking.

So we know
A1=K
A2 therefore =-2k/3 Because A2=-2(k)/3
A3= 4k/9 because A3 = -2(a2)/3 = -2 ((2k/3)/3) which equals 4k/9
A4 = -8k/27
A5 = 16K/81
A6 = -32K/243

So now we need to look at the solutions. Breaking the numbers into prime factorization is the trick for this part.

1) 3 well we can see that A5 =(16*3)/81 is not an integer
2) 16 is wrong as A5 = (2^4) * (2^4) / (3^4). Well (2^8) /(3^3) is clearly not an integer
3) 108 is wrong as A5 = [(2^4)* (9X13)] / 9^2 . Again we only have one power of 9 on the top and 2 on the bottom. Clearly not an integer
4) 162 = (9^2)* (2^4) / 9^2 this will be an integer

and A6 = -[2^5 * (9^2) *2)] / (9^2 X 3). Notice we have an extra 3 on the bottom therefore this isn't an integer.

5) We can solve E for fun
A5= [(2^5) * (9^2)*3] / [(9^2)X 3] Clearly an integer
A6= 243=(9^2) X 3 . so [(2^5) X (9^2 )*3] / [(9^2) X 3] Clearly an integer

But this answer is wrong for 5), since you're dividing a5 by 9^2 *3, when you should really just be dividing by 9^2.

9^2 makes it easier for it to be an integer. That is a typo and I can fix it but the answer is still 100% correct. If 9^2 X 3 is an integer then it's much easier for plain old 9^2 to be an integer.

Kudos [?]: 1 [0], given: 4

Re: A term an is called a “cusp” of a sequence if an is an integer but an+   [#permalink] 24 Aug 2017, 10:40
Similar topics Replies Last post
Similar
Topics:
5 For positive integers n, the integer part of the nth term of sequence 5 27 Apr 2015, 01:52
5 The first term of a sequence of consecutive positive even integers is 4 03 Jun 2017, 11:13
20 For every positive integer n, the nth term of a sequence is 10 26 Jul 2017, 06:24
6 There is a sequence where each term is a positive integer and at least 1 23 Feb 2017, 23:56
2 There is a sequence such that each term is positive integer and each d 4 16 Aug 2016, 07:37
Display posts from previous: Sort by


text:
#### Volume 10, issue 2 (2006)

 Download this article For screen For printing
 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editorial Interests Editorial Procedure Submission Guidelines Submission Page Ethics Statement Author Index To Appear ISSN (electronic): 1364-0380 ISSN (print): 1465-3060 Other MSP Journals
The integral cohomology of the group of loops

### Craig A Jensen, Jon McCammond and John Meier

Geometry & Topology 10 (2006) 759–784
 arXiv: 0903.0140
##### Abstract

Let denote the group that can be thought of either as the group of motions of the trivial $n$–component link or the group of symmetric automorphisms of a free group of rank $n$. The integral cohomology ring of is determined, establishing a conjecture of Brownstein and Lee.

##### Keywords
nonpositive curvature, CAT(0), decidability
Primary: 20J06
Secondary: 57M07
##### Publication
Received: 16 October 2005
Revised: 6 February 2006
Accepted: 3 June 2006
Published: 11 July 2006
Proposed: Benson Farb
Seconded: Joan Birman, Walter Neumann
##### Authors
 Craig A Jensen Department of Mathematics University of New Orleans New Orleans, LA 70148 USA Jon McCammond Department of Mathematics University of California Santa Barbara, CA 93106 USA John Meier Deptartment of Mathematics Lafayette College Easton, PA 18042 USA


text:
# Notation: Set where function is positive

Given some function $f: X \to \mathbb{R}$ from some space $X$ to the reals.

I have sometimes seen the notation $\{f > 0\}$ used to denote the set $\{x \in X : f(x) > 0 \}$. Is this a common/usual notation?

I would like to use the shorter one because it is easier to write. But the longer one is more clear. Which one is more natural?

• You answered yourself. The longer one is more clear and the shorter one is easier to write. And yes the shorter one is common ! – alkabary Jul 10 '15 at 23:23
• @alkabary ok perfect, thank you :) – Loreno Heer Jul 10 '15 at 23:23
• You could also write $f^{-1}((0,\infty))$. – Ben Whitney Jul 10 '15 at 23:40
• Notice that the shorter notation is very common in fields like measure theory, probabilistic theory, and related fields. It less common in general. – user251257 Jul 11 '15 at 0:19
• @BenWhitney: Why not simply $f^{-1}(\mathbb R^+)$? – celtschk Jul 11 '15 at 10:18

The shorter notation $\left\{f > 0\right\}$ is shorter and is very common in fields such as measure theory. It is less common but still occasionally seen in other fields. It's obviously not as clear as the longer notation.


text: The general stringparam author-tools may be set to yes to activate special handling of the <todo> element, the @provisional attribute of an <xref> element, and notation and index entries. The -specific stringparam latex.draft set to yes will automatically activate the previous features, in addition to a few others appropriate to the printed page. We have an XSL stylesheet that dumps every <todo> and every @provisional attribute to the screen as a simply-formatted text report, but it is not public now.


text:
# Topology exercise - open, closed and bounded sets in $\mathbb{R}^n$

Would someone check my solution to this exercise:

Exercise. Determine whether the following subsets of $\mathbb{R^2}$ are open, closed, and/or bounded.

1. $A=\{\|x\|\le1\}$
2. $B=\{\|x\|=1\}$
3. $C=\{\|x\|\lt1\}$
4. $D=\{\text{the x-axis}\}$
5. $E=\mathbb{R^2}-\{\text{the x-axis}\}$
6. $F=\{(x,y):x \text{ and } y \text{ are integers}\}$
7. $G=\{(1,0),(1/2,0),(1/3,0),\dots\}$
8. $H=\mathbb{R^2}$
9. $I=\emptyset$

Solution.

First, define a set $A$ to be open if every $x\in A$ is an interior point and to be closed if every $x\notin A$ is an exterior point. LET $B(x,\epsilon)$ denote the open ball of radius $\epsilon$ centered at $x$.

1. Let $x\notin A$. Then $B(x,\epsilon)$ is a neighborhood of $x$ with $\epsilon=\|x\|-1$ So $A$ is closed. $A$ is not open because points $x$ with $\|x\|=1$ have neighborhoods that contain points not in $A$. $A$ is bounded because $A\subseteq B(0,2)$
2. Closed (but not open) and bounded (as above).
3. Open but not closed (because points $x$ with $\|x\|=1$ intersect $C$). $C$ is bounded (a ball of radius $2$ contains $C$)
4. Closed, not open, not bounded.
5. Open, not closed, not bounded.
6. Closed, not open, not bounded.
7. Closed, not open, bounded ($\subseteq B(0,2)$)
8. Open, closed (vacuously true), not bounded.
9. Open (vacuously true), closed, bounded.

Except for number 7, you're correct. Is the origin an exterior point of $G$?

Incidentally, the only subsets of $\Bbb R^2$ (in the usual metric-induced topology) that are both closed and open are $\Bbb R^2$ and $\emptyset$. This is a fact you might want to keep in mind for future problems.

• Thank you! A ball around 0 must include positives in the set so it's not closed. CorrecT? – saadtaame Jul 19 '13 at 12:51
• That's correct! – Cameron Buie Jul 19 '13 at 12:52
• Are limit points the same as the ones we study in calculus ($lim$) – saadtaame Jul 19 '13 at 12:54
• Indeed, the concepts are closely related. We can talk about limits of functions as we approach limit points of their domain, for example. That question is a bit too broad to be answered fully in a single comment, but I suspect that it has been asked before on this site, so you might take a look and see if you can find it. – Cameron Buie Jul 19 '13 at 12:56

For $7.$ the sequence $(1/n,0)$ is convergent to $(0,0)\not \in$ the set.

For $1.2.3)$ you can use also the continuous function $f\colon\mathbb R^n\rightarrow \mathbb R,x\mapsto ||x||$ and the fact that the preimage of closed (open) set by a continuous function is closed (open).

• Thanks! It's the first exercise in the book. So no resort to continuity or advanced stuff. – saadtaame Jul 19 '13 at 12:48


text:
CosmoCoffee

 FAQ   Search  SmartFeed   Memberlist    Register Profile   Log in Arxiv New Filter | Bookmarks & clubs | Arxiv ref/author:

 [1003.3451] Primordial Non-Gaussianity and the NRAO VLA Sky Survey
 Authors: Jun-Qing Xia, Matteo Viel, Carlo Baccigalupi, Gianfranco De Zotti, Sabino Matarrese, Licia Verde Abstract: The NRAO VLA Sky Survey (NVSS) is the only dataset that allows an accurate determination of the auto-correlation function (ACF) on angular scales of several degrees for Active Galactic Nuclei (AGNs) at typical redshifts $z \simeq 1$. Surprisingly, the ACF is found to be positive on such large scales while, in the framework of the standard hierarchical clustering scenario with Gaussian primordial perturbations it should be negative for a redshift-independent effective halo mass of order of that found for optically-selected quasars. We show that a small primordial non-Gaussianity can add sufficient power on very large scales to account for the observed NVSS ACF. The best-fit value of the parameter $f_{\rm NL}$, quantifying the amplitude of primordial non-Gaussianity of local type is $f_{\rm NL}=62 \pm 27$ ($1\,\sigma$ error bar) and \$25

Author Message
Patrick McDonald

Joined: 06 Nov 2004
Posts: 17
Affiliation: CITA

 Posted: March 19 2010 This paper claims to find ~3 sigma evidence for local-form non-Gaussianity based on a measurement that the NVSS correlation function does not go to zero by separations ~8 degrees, when it should have been consistent with zero by ~2−3 degrees for standard Gaussian LCDM (given their error bars). My first question when seeing any correlation function that "does not go to zero" is "doesn't any measured correlation function *need* to become consistent with zero as you go to large separations, and why haven't the authors shown me that theirs does??" In other words: you may or may not have built in an integral constraint that forces your points to go negative somewhere, but in any case you should have a term in the covariance matrix corresponding to adding a constant to the correlation function, which guarantees that any fit results will not be sensitive to a shift in the mean of the survey (or scales much larger than the ones you think you can control). It looks to me like the authors' measurement is essentially completely based on this kind of constant term in the correlation function, i.e., if I am allowed to add a constant to the Gaussian case, it doesn't look like it can be distinguished from the non-Gaussian case. If the authors have some reason to believe this is not a problem, it should be clarified in the paper. That is a general observational consideration (you can't measure fluctuations in the mean of your survey), but there is a related theoretical issue: Naively, the constant contribution to the correlation function is infinite in this model for non-Gaussianity (although they may be leaving out the part of the calculation that gives that), so it is not clear what their predictions that look like they are going flat at large separations mean. There is an easy solution to both problems: marginalize over a free constant added to the correlation function prediction. It seems pretty clear though that they will find nothing of any significance when doing this. This is really a general problem with the correlation function. Looking at it at a given separation does not really correspond to what one is intuitively thinking when thinking about a certain "scale", e.g., the value at a relatively small separation is affected by fluctuations in something as large-scaled as the mean of the survey. Usually this doesn't matter, however, because one has measurements showing that the correlation goes to zero on scales larger than the ones of interest (to better precision than the changes of interest on your scale), which implicitly constrain the kind of constant term you should generally marginalize over.
Carlos E Cunha

Joined: 19 Mar 2010
Posts: 1
Affiliation: U. of Michigan

 Posted: March 19 2010 The authors do claim to take into account the integral constraint. At the end of Sec. 4 they state that "the correction proposed by Wands & Slozar (2009) to account for the infrared divergence of the non-Gaussian halo correlation function is fully negligible for our best-fit fnl value". The Wands & Slozar correction is just the sample variance at the scale of the survey. But, considering how large their best-fit fnl is and the volume of the survey. it is surprising that they find that the correction is negligible.
Patrick McDonald

Joined: 06 Nov 2004
Posts: 17
Affiliation: CITA

 Posted: March 19 2010 The basic problem doesn't really have anything to do with fNL, and isn't really accessible to a calculation of corrections. It is basically just: if your correlation function is positive at every separation you say you trust, you necessarily have sensitivity to constant shifts coming from larger scale structure, whether it is real large-scale structure or just systematic errors in the measurement.
Jun-Qing Xia

Joined: 02 Jan 2005
Posts: 22
Affiliation: SISSA, Italy

 Posted: March 24 2010 Unfortunately, in the small space for a Letter we could not spend too many words on reviewing the literature on the NVSS correlation function in general. Here's some additional information that may be useful to understand the issue. The radio sources and in particular NVSS auto correlation function has been studied exahustively. References include: Cress et al 1996, Cress & Kamionkowski 1998, Magliocchetti et al 1998, Blake and Wall 2002a (Mon.Not.Roy.Astron.Soc. 329 (2002) L37- L41), Blake and Wall 2002b (Mon.Not.Roy.Astron.Soc. 337 (2002) 993), Negrello et al 2006(Mon.Not.Roy.Astron.Soc.377:1557−1568,2007) and (Mon.Not.Roy.Astron.Soc.368:935−942,2006) ) Both FIRST and NVSS surveys since the first analyses showed that their correlation function did not have the same shape as expected in a standard LCDM model; one would have to play with the sources redshift distribution and biasing to make them match (for a heat-to- head comparison of FIRST and NVSS see Blake and Wall 2002b). Blake and Wall 2002a present probably the first robust determination of the NVSS correlation function. There they show that the correlation function is well described by two power laws: at small scales (separations of less than 0.1 degrees) one sees the effect of the size distribution of the sources (these are not points at these frequences and these resolutions) and at larger scales one sees the sources clustering. In our paper we exclude the small scales as we are not interested on the sources sizes. The large scales, >0.1 deg <10 deg,(where "large" is still small compared to the survey size), where one should see the clustering properties, may be to some extent affected by systematic effects involving non-uniform source sampling. In Blake & Wall 2002a sec 2.3 it is discussed how the effect of varying source density may enhance the correlation function. There they quantify that the effect depends on the flux cut, it is very small for sources >10mJy but increases rapidly below that flux cut. We work at the high flux cut and anyway report what happens when we apply a possible correction (the 10−4 mentioned). This is a conservative choice, see sec 4.3 of Blake and Wall 2002b and 2.3 of Blake and Wall 2002a. The correlation function we measure is fully consistent with the Blake \& Wall one (see discussion at the end of page 4 where we swapped our data and errors with the Blake&Wall ones). The part of the correlation function least affected by possible density gradients (arising from the difficulty in calibrating and matching the different configurations of the array-see discussion in Blake & Wall) is at separation <10 deg. In order to zoom in on the interesting part of the correlation function we use and show only scales up to 8 degrees separation. We are throwing away data -and information- at larger separation, but scales <10 deg are most reliable. The survey's large sky coverage allows us to compute the correlation to much larger separations. In fact the mean of the survey is computed from the full survey but then only correlations at separations <9 deg are shown. To see an example of the correlation function to larger separations see for example fig 10 of Hernandez-Monteagudo 2009 (0909.4294), concentrating on the blue/green symbols. In addition to that it may still be that non-zero fnl includes extra fluctuations (see discussion in Wands and Slosar) on the survey size. We compute that this effect is fully sub-dominant compared to the un-uniform source density effect and anyway does not change the results (that is the meaning of the sentence "the correction proposed by Wands & Slozar (2009) to account for the infrared divergence of the non-Gaussian halo correlation function is fully negligible for our best-fit fnl value".). Indeed the theoretical variance on the scale of the survey is 5e−5 × fNL/fNL(best fit), which is smaller than the effect due to density gradients for all fNL<100. So to summarize: the correlation function does go to zero on large (>10 deg) scales but , whatever we do, a) these are larger than the scales of interests here b) it does not do it as sharply and at the scales predicted by LCDM ( ~2 degrees) for a biasing model for the sources in agreement with that of their optical counterpart. There are several ways out, each of them involve some "non-standard" solution: a) a bias model which decreases with z, based on a redshift dependent hosting halo mass (but then radio loud and radio quiet sources are not the same beast) see papers by Massardi et al 2010 and refs there. b) primordial non-gaussianity (but then you will have do be willing to drop gaussianity) c) some other systematic error in the survey that we could not find or think of d) a combination of different effects (mis-estimate of off diagonal covariance terms +strange bias evolution + strange Mmin+ bigger correction due to source density gradients than quantified by Blake and Wall) , each of them making our error-bars slightly underestimated 'til the integrated effect of all gives an fnl consistent with zero. The literature so far had concentrated on option a), so we hope we have opened the discussion about b). It is surely early to draw any definitive conclusions, but still one can conclude -as we do- that "our work should be seen as a “proof of principle”, indicating that future surveys probing scales ~ 100 Mpc at substantial redshifts can put stringent constraints on primordial non-Gaussianity". I hope this answers your questions, but please ask if you need further clarifications.
Anze Slosar

Joined: 24 Sep 2004
Posts: 205
Affiliation: Brookhaven National Laboratory

 Posted: March 24 2010 I am still confused about some of the issues here. The correlation function must do more than just go to zero at large scales, it must integrate to zero, which means it must necessarily go below zero at large separations. At what distance does your correlation function actually go through zero? Could we se xi(theta)theta2 plotted for some large values of theta? I also disagree with Pat on the importance of this effect. What one is doing is essentially forcing integral constraint by setting mean n to the mean n of the survey, which is different from the mean n of the universe. This essentially ignores modes larger than survey. But it doesn't matter for large surveys because cosmic mean n is going to be pretty close to measured mean n. But true, it is still the safest to marginalise over it. Also, in Wands and Slosar (for definition of Slozar (note z) , see http://www.urbandictionary.com/define.php?term=slozar ) we worked out, how to calculate xi to be compared with observations, because xi, when calculated from P(k) is formally divergent for any r. So in that sense it is not a correction, because it takes you from infinity to a finite value. But I agree that this is not the only possible way to calculate theory to be compared with your observations and I tend to trust Matarrese and Verde....
Patrick McDonald

Joined: 06 Nov 2004
Posts: 17
Affiliation: CITA

 Posted: March 25 2010 If you don't trust scales >R, it seems like the most often correct thing to do would be to high-pass filter both the theory and observations to remove the power on scales >R. This would remove a constant from the correlation function at separations <
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT + 5 Hours Page 1 of 1

 Jump to: Select a forum Arxiv paper discussion----------------arXiv papers Topic discussion----------------Early UniverseCosmological ModelCosmological Observations  Projects and Resources----------------Computers and softwareTeaching, Papers and PresentationsResearch projectsiCosmo Coming up----------------Job vacanciesConferences and meetings Management----------------CosmoCoffee
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group. Sponsored by WordWeb online dictionary and dictionary software.


text:
# Irregular expressions

Tavian Barnes GitHub

Regular expressions are fascinating to me. On one hand, they can be extremely succinct, expressive, and efficient. On the other hand, they can be basically write-only. They come with a simple but powerful theory that leads to efficient implementations. Sadly, many implementations ignore the theory in order to offer additional features, at the cost of worst-case exponential complexity.

It is possible, however, to implement some of those additional features, and still operate in worst-case linear time. It was pointed out to me by Geoff Langdale and Evgeny Kapun that my implementation of those additional features is incorrect. I've hidden the wrong implementations for now. The implementation (~400 lines of Rust) even fits in a single blog post! The full code is on GitHub, and the commit history lines up with the blog post if you want to follow along.

## State machines

The key to worst-case linear running time is to use Nondeterministic Finite Automata (NFAs). An NFA is basically a flow chart for deciding whether to accept or reject a string. The N in NFA means that multiple states can be active at the same time.

Before actually implementing NFAs, it's nice to start with an interface for them:

/// A regular expression matcher.
trait Matcher {
/// Activate this matcher's *start* state.
fn start(&mut self) -> bool;

/// Process a character from the string we're matching against.
fn push(&mut self, c: char) -> bool;
}

A Matcher starts out with no active states. Matcher::start() activates the start state, and returns whether the matcher is currently in an accepting state (which could happen if, for example, the regex matches an empty string). To test if a string matches, you feed its characters one-by-one to Matcher::push(), or just call this helper method to do it for you:

trait Matcher {
...
/// Test if a string matches.
fn matches(&mut self, text: &str) -> bool {
text.chars().fold(self.start(), |_, c| self.push(c))
}
}

Commit

The simplest regex is the empty regex, so let's start with that.

/// A regular expression.
enum Regex {
/// The empty regex.
Empty,
}

The empty matcher has only one state.

/// Matcher for Regex::Empty.
#[derive(Default)]
struct Empty {
matched: bool,
}

impl Matcher for Empty {
fn start(&mut self) -> bool {
self.matched = true;
true
}

fn push(&mut self, _: char) -> bool {
self.matched = false;
false
}
}

It would be convenient if we could parse regexes instead of having to write things like Regex::Empty explicitly. We can use nom to build a parser, starting with a simple grammar.

/// Parser implementation.
fn regex(pattern: &str) -> IResult<&str, Regex> {
let empty = success(Regex::Empty);

let group = delimited(char('('), regex, char(')'));

alt((group, empty))
.parse(input)
}

## Dot dot dot

Commit

The next-simplest regex is the . metacharacter, which matches any character.

enum Regex {
...
/// Matches any one character.
Dot,
}

The matcher for . has two states.

/// Matcher for Regex::Dot.
#[derive(Default)]
struct Dot {
started: bool,
matched: bool,
}

impl Matcher for Dot {
fn start(&mut self) -> bool {
self.started = true;
self.matched
}

fn push(&mut self, _: char) -> bool {
self.matched = self.started;
self.started = false;
self.matched
}
}

It's a small addition to the parser as well.

fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let dot = char('.').map(|_| Regex::Dot);

alt((dot, group, empty))
.parse(input)
}

## Literally me

Commit

The next regex to support is character literals like c that match only themselves.

enum Regex {
...
/// Matches a literal character.
Literal(char),
}

The matcher for literals is very similar to Dot.

/// Matcher for Regex::Literal.
struct Literal {
c: char,
started: bool,
matched: bool,
}

impl Matcher for Literal {
fn start(&mut self) -> bool {
self.started = true;
self.matched
}

fn push(&mut self, c: char) -> bool {
self.matched = self.started && c == self.c;
self.started = false;
self.matched
}
}

The parser is extended with support for literals, as well as escape sequences like \. to allow matching metacharacters literally.

fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let meta = r"\().";

let literal = none_of(meta).map(Regex::Literal);

let escape = preceded(char('\\'), one_of(meta))
.map(Regex::Literal);

alt((literal, escape, dot, group, empty))
.parse(input)
}

## A star is born

Commit

So far our regexes can only match up to a single character. The next step is to support the Kleene star operator *, for regexes like a* that match "", "a", "aa", "aaa", etc.

enum Regex {
...
/// Matches zero or more repetitions.
Star(Box<Regex>),
}

The NFA for the * operator adds a loop with $\varepsilon$-transitions to let the pattern match multiple times. It doesn't even need any states of its own.

/// Matcher for Regex::Star.
struct Star<A>(A);

impl<A: Matcher> Matcher for Star<A> {
fn start(&mut self) -> bool {
self.0.start() || true
}

fn push(&mut self, c: char) -> bool {
self.0.push(c) && self.start()
}
}

To parse the * operator properly we have to shuffle some grammar rules around.

fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let meta = r"\().*";
...
let atom = alt((literal, escape, dot, group));

let repeat = flat_map(atom, |r| fold_many0(
char('*'),
move || r.clone(),
|r, _| r.star(),
));

alt((repeat, empty))
.parse(input)
}

## One is the loneliest number

Commit

It's a bit sad that our regexes can currently only have one (non-meta) character. We can handle a, a*, and even the questionably-useful a**, but in order to support regexes like ab*c, we need our first binary operator: concatenation.

enum Regex {
...
/// Matches two patterns in a row.
Concat(Box<Regex>, Box<Regex>),
}

The matcher for concatenated patterns connects the accept state of the first to the start state of the second.

/// Matcher for Regex::Concat.
struct Concat<L, R> {
left: L,
right: R,
right_started: bool,
}

impl<L: Matcher, R: Matcher> Matcher for Concat<L, R> {
fn start(&mut self) -> bool {
if self.left.start() {
self.right_started = true;
self.right.start();
} else {
false
}
}

fn push(&mut self, c: char) -> bool {
let mut ret = false;

if self.right_started {
ret |= self.right.push(c);
}

if self.left.push(c) {
self.right_started = true;
ret |= self.right.start();
}

ret
}
}

Just one more grammar rule is all we need to parse concatenations.

fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let word = many1(repeat)
.map(|v| reduce(v, Regex::concat));

alt((word, empty))
.parse(input)
}

## This or that

Commit

Our next feature is the alternation operator |, which lets us match either (or both) of two patterns.

enum Regex {
...
/// Matches either of two patterns.
Or(Box<Regex>, Box<Regex>),
}

The matcher for alternations joins both patterns together with $\varepsilon$-transitions.

/// Matcher for Regex::Or.
struct Or<A, B>(A, B);

impl<A, B> Matcher for Or<A, B>
where
A: Matcher,
B: Matcher,
{
fn start(&mut self) -> bool {
self.0.start() | self.1.start()
}

fn push(&mut self, c: char) -> bool {
self.0.push(c) | self.1.push(c)
}
}

A couple more grammar rules are all we need.

fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let meta = r"\().*|";
...
let chunk = alt((word, empty));

separated_list1(char('|'), chunk)
.map(|v| reduce(v, Regex::or))
.parse(pattern)
}

## Feature-complete

The features we implemented so far are enough to express every regular language—in other words, to match anything that could be matched by a regular expression. Actually, we didn't even need ., though it would be very inconvenient to have to write

(a|b|c|...|A|B|C|...|0|1|2|...|!|@|#|...)

There are still a few other features that regex engines commonly provide, such as the + (repeat 1 or more times) and ? (match 0 or 1 times) operators, that we could easily implement.

enum Regex {
...
/// Matches one or more repetitions.
Plus(Box<Regex>),
/// Matches zero or one times.
Maybe(Box<Regex>),
}
fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let meta = r"\().*|+?";
...
let repeat = flat_map(atom, |r| fold_many0(
one_of("*+?"),
move || r.clone(),
|r, c| match c {
'*' => r.star(),
'+' => r.plus(),
'?' => r.maybe(),
_ => unreachable!(),
},
));
...
}

We don't even need any new matchers; we can just re-use existing ones.

impl Regex {
/// Compile a regular expression.
fn matcher(&self) -> Box<dyn Matcher> {
match self {
...
Self::Plus(a) => Box::new(
// A+ is the same as AA*
a.matcher().concat(a.matcher().star())
),
Self::Maybe(a) => Box::new(
// A? is the same as (A|)
a.matcher().or(Empty::default())
),
}
}
}

We're also missing character classes like [a-z], but this post is already long enough without them. They could be handled like Regex::Literal but with a list of ranges instead of a single char.

Everything below this point is actually incorrect. Click to show it anyway.

## Not doing the work

Commit

Regular languages are closed under complement, which means that for every regex there is another that matches the exact opposite set of strings. Unfortunately, this complementary regex can be pretty ugly. Even a simple one like hello has a pretty terrible complement:

|([^h]|h[^e]|he[^l]|hel[^l]|hell[^o]|hello.).*

Typically, users negate their matches on a layer above the regex syntax itself, like with grep -v or if !regex.matches(text). But sometimes it would be useful to have dedicated syntax for inverting a regex, especially just part of a regex. We can invent a ! operator to express this.

enum Regex {
...
/// Matches the opposite of a pattern.
Not(Box<Regex>),
}
fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let meta = r"\().*|+?!";
...
let not_word = many0_count(char('!'))
.and(word)
.map(|(n, r)| {
(0..n).fold(r, |r, _| r.not())
});

let chunk = alt((not_word, empty));
...
}

Now we can write the opposite of hello much more simply: !hello.

Finding the complement of an arbitrary NFA is expensive: you first convert the NFA to a DFA, which can blow up its size exponentially, and then flip the accepting/rejecting states. Lucky for us, we don't have to.

/// Matcher for Regex::Not.
struct Not<A>(A);

impl<A: Matcher> Matcher for Star<A> {
fn start(&mut self) -> bool {
!self.0.start()
}

fn push(&mut self, c: char) -> bool {
!self.0.push(c)
}
}

This is the key insight of the whole post: rather than actually finding the complement of an NFA, we can just write a Matcher implementation that acts like it. The ! operator lets us easily match things like "lines that don't contain hello", but it also opens the door to another more useful feature.

## Yes, and

Commit

Sometimes we might have two patterns and want both of them to match. For example, we might want to find lines that contain both hello and world. Regular languages are also closed under intersection, so we should be able to write such a regex. Again, though, it might be pretty long.

.*hello.*world.*|.*world.*hello.*

This quickly gets out of hand with more than two patterns. But with the ! operator, we can use one of De Morgan's laws,

(A && B) == !(!A || !B)

to do the same thing without repeating ourselves:

!(!(.*hello.*)|!(.*world.*))

This is still not the easiest regex to read (strings that don't (not contain hello) or (not contain world)), so let's add an & operator to express the concept more directly:

(.*hello.*)&(.*world.*)

enum Regex {
...
/// Matches the intersection of two patterns.
And(Box<Regex>, Box<Regex>),
}
fn regex(pattern: &str) -> IResult<&str, Regex> {
...
let meta = r"\().*|&";
...
let clause = separated_list1(char('&'), chunk)
.map(|v| reduce(v, Regex::and));

separated_list1(char('|'), clause)
.map(|v| reduce(v, Regex::or))
.parse(pattern)
}

We don't even need a new matcher,

impl Regex {
/// Compile a regular expression.
fn matcher(&self) -> Box<dyn Matcher> {
match self {
...
Self::And(a, b) => Box::new(
a.matcher().not()
.or(b.matcher().not())
.not()
),
}
}
}

but it's not hard to write one anyway.

/// Matcher for Regex::And.
struct And<A, B>(A, B);

impl<A: Matcher, B: Matcher> Matcher for And<A, B> {
fn start(&mut self) -> bool {
self.0.start() & self.1.start()
}

fn push(&mut self, c: char) -> bool {
self.0.push(c) & self.1.push(c)
}
}

## Looking around

As far as I know, our ! and & operators are not features of any major regex implementation. But a similar feature called lookaround or positive/negative lookahead/lookbehind is found in many regex engines.

FeatureSyntaxIrregex equivalent
Positive lookaheadA(?=B)CA((B.*)&C)
Negative lookaheadA(?!B)CA((!B.*)&C)
Positive lookbehindA(?<=B)C(A&(.*B))C
Negative lookbehindA(?<!B)C(A&(!.*B))C

As far as I know, this feature is only provided by regex engines that have worst-case exponential complexity. The two major worst-case linear regex engines that I'm aware of, RE2 and Rust's regex crate, don't support it.

As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported.

Notably, backreferences and arbitrary lookahead/lookbehind assertions are not provided. In return, regular expression searching provided by this package has excellent worst-case performance.

But as this post shows, it is certainly possible to support lookaround (not backreferences!) in linear time. There are some unanswered questions (what about capture groups?), but I'm curious if this implementation strategy would be workable in a production-quality regex engine.